Так как путь напрямую не подходит по условию

По всем вершинам тогда

Да, сорри

Только не a,b. А координаты

X,y

Так как путь напрямую не подходит по условию

А это не следует из условия пока

А это не следует из условия пока

Найти "через другие вершины"

Там написано

Единственное что понятно

Path = [(x,y),(x,y)..]

Найти "через другие вершины"

Это значит через все другие, через любую другую, через подмножество вершин?

:)

Найти "через другие вершины"

Все верно

А вот это уже непонятно

Через другие может значит что "через другую" не подходит

Надо в начальной школе про кванторы рассказывать

Нужна исходная формулировка

Желательно в виде фото

А то тоже криво перенаберет

Через все другие - NP-трудная задача, через непустое множество вершин - перебор промежуточной, через любое множество вершин - напрямую

Через все другие - NP-трудная задача, через непустое множество вершин - перебор промежуточной, через любое множество вершин - напрямую

Np-трудная значит лишь что он может не дождаться если много вершин

Есть список координат points. Берём рандомную начальную точку (x0,y0) и конечную (x1,y1). Между этими точками по точкам из points необходимо проложить путь.

Так понятнее выразился?

Нет

Что не понятно?

Что значит путь по точкам? Можно формально?

Все то же самое

Все те же три варианта

Есть список координат points. Берём рандомную начальную точку (x0,y0) и конечную (x1,y1). Между этими точками по точкам из points необходимо проложить путь.

Покажи как тебе задание дали

Если множество точек не линейно связно, это, вообще говоря, невозможно

Опять же про краткость пути непонятно. Какая метрика?

Связаны линейно все точки

Опять же про краткость пути непонятно. Какая метрика?

Ну я считал через hypot

Связаны линейно все точки

То есть их как минимум континуум

А как они вводятся в конечную память?

Точек ограниченное количество. Пусть будет 50 например

А как они вводятся в конечную память?

Не понял вопроса

Евклидовая, манхеттоновская, констант

Евклидовая

Задание покажи

Не выдумывай

Судя по тому, что надо найти путь, вариант всего один

Это не учебное задание. Пишу для себя

Столкнулся с такой задачей просто

Где столкнулся?

Обрабатываю диаграмму вороного, но это не суть

Что надо сделать с диаграммой и как там поможет поиск кратчайшего пути?

Что надо сделать с диаграммой и как там поможет поиск кратчайшего пути?

Есть список точек. Нужно найти самый короткий путь по другим точками между двух рандомно взятых точек

Как ещё это объяснить)

Соединить точки нужно прямыми линиями

Напиши формальное определеное "пути по точкам"

Ну есть например 2д изображение карты. Начальная точка - Москва. Конечная - Питер. Нужно между этими городами найти самый короткий путь по другим городам.

Только прямыми линиями

Например, путь это последовательность точек длины не менее 2, первый элемент которой совпадает с начальной точкой, последний с конечной, и все ее элементы различны

Хороший пример

Вот в таком стиле, пожалуйста, а не примерами

Ну есть например 2д изображение карты. Начальная точка - Москва. Конечная - Питер. Нужно между этими городами найти самый короткий путь по другим городам.

Напрямую

Либо цикл по всем городам и путь с одной пересадкой

Если напрямую нельзя

Напрямую

Прямой дороги нет, только по другим городам

Хоть где-то есть прямая дорога?

До всех других городов прямая

Есть список точек. Нужно найти самый короткий путь по другим точками между двух рандомно взятых точек

Напоминает задачку, которую я когда-то решал... Только было еще ограничение в "максимальную длину прыжка"

Тогда цикл и одна пересадка

потому что иначе ответ это "просто прямо из А в Б"

Тогда цикл и одна пересадка

Подробнее?

ERROR: S client not available

Напоминает задачку, которую я когда-то решал... Только было еще ограничение в "максимальную длину прыжка"

А тут уже дейкстра, наверное

для большого количества точек получалось проблемно

в итоге был сделан "жадный" алгоритм, который просто выбирал такую точку, до которой скалярное произведение "в сторону финиша" и "до этой точки" было бы максимальным

но такой алгоритм может завести в тупик - и заводил

А если жадный алгоритм совместить с дейкстрой, получится А*

еще момент - на практике требовалось в каждый момент времени найти только один - первый - хоп

после этого в течение какого-то времени корабль летит. После совершения прыжка ситуация может уже поменяться

Прямой дороги нет, только по другим городам

Т.е. можно сформулировать так если длина перпендикуляра от третьего города на прямую между двумя городами меньше половины этой прямой, то путь должен проходить через этот город?

Т.е. можно сформулировать так если длина перпендикуляра от третьего города на прямую между двумя городами меньше половины этой прямой, то путь должен проходить через этот город?

Да, все верно

Т.е. можно сформулировать так если длина перпендикуляра от третьего города на прямую между двумя городами меньше половины этой прямой, то путь должен проходить через этот город?

Блин, точно)

Пишу, рисую с телефона. Но думаю понятно

Т.е. можно сформулировать так если длина перпендикуляра от третьего города на прямую между двумя городами меньше половины этой прямой, то путь должен проходить через этот город?

Как только это реализовать?

Координаты заданы на плоскости (x, y)?

Координаты заданы на плоскости (x, y)?

Да, в виде списка

вот да, у меня есть ощущение, что тут есть ограничение на дальность прыжка

и координаты небось целочисленные

и координаты небось целочисленные

Да

и еще одна догадка - координаты зациклены 8)

Да, условия не очень точные, их, хотя бы для себя надо сформулировать точно (например, как я выше сформулировал)

и еще одна догадка - координаты зациклены 8)

Что это значит?

Что именно не точно?

ребята

кто может помочь

смотрите

я смотрел видео по созданию бота

и вот автор видео открыл файл как то

https://youtu.be/LJdu68ro-rU?t=2607

тут таймкод привязан

подскажете как он открыл этот файл?

и где