Найти кратчайший путь

@MaMush · Регистрация: 05.10.2020

Студворк — интернет-сервис помощи студентам

Всем доброго дня и больше свободного времени!
Мне вот вдруг пришлось окунуться в мир алгоритмов, который я не очень люблю, ибо такими не особо владею. Прошу не начинать объяснять, что они мне нужны и тд, что многие делают, а помочь).
Задача - даны координаты точек (x, y) в виде массива с кортежами (в целом ввод не важен, это лишь часть программы, данные зависят от меня). Требуется кратчайшим образом пройтись по ВСЕМ координатам.
Нашел в инете только между 2 точкам, при этом не проходя другие.

Кому интересно - задача про облет кратчайшим путем квадрокоптером координат точек определенного цвета.

@Catstail · 26.11.2021, 09:11

Сколько точек?

@Gdez · 26.11.2021, 10:19

MaMush, может так?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def dist(p):
    
    return(abs(complex(p[0]-origin[0], p[1]-origin[1])))
 
 
n = 8 #int(input('количество точек: '))
points = {(3,4),(5,3),(7,4),(8,6),(7,8),(3,8),(2,6),(5,9)} #{tuple(map(float, input().split())) for _ in range(n)}
origin = (0,0)
origin = max(points, key=lambda a: dist(a))
res = [origin]
points.discard(origin)
 
for i in range(n-1):
    origin = min(points, key=lambda a: dist(a))
    res.append(origin)
    points.discard(origin)
 
print(res)

@eaa · 26.11.2021, 10:57

Сообщение от Catstail

Сколько точек?

если только на х, у будут ограничения.

@Catstail · 26.11.2021, 11:20

Gdez, говорят, что в данной задаче жадный алгоритм не дает полной оптимизации

@Gdez · 26.11.2021, 11:50

Catstail, Но ведь по любому для каждой точки приходится находить ближайшую, перебирая оставшиеся...

@Catstail · 26.11.2021, 16:25

Gdez, это и есть "жадный алгоритм". Он даст приемлемое решение, но не обеспечивает глобальной минимальности.

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@MaMush 4 / 9 / 2 Регистрация: 05.10.2020 Сообщений: 51

	Найти кратчайший путь 25.11.2021, 19:59. Показов 1602. Ответов 6 Метки python, олимпиады (Все метки) Всем доброго дня и больше свободного времени! Мне вот вдруг пришлось окунуться в мир алгоритмов, который я не очень люблю, ибо такими не особо владею. Прошу не начинать объяснять, что они мне нужны и тд, что многие делают, а помочь). Задача - даны координаты точек (x, y) в виде массива с кортежами (в целом ввод не важен, это лишь часть программы, данные зависят от меня). Требуется кратчайшим образом пройтись по ВСЕМ координатам. Нашел в инете только между 2 точкам, при этом не проходя другие. Кому интересно - задача про облет кратчайшим путем квадрокоптером координат точек определенного цвета. 0

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	26.11.2021, 09:11
	Сколько точек? 0

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	26.11.2021, 11:20
	Gdez, говорят, что в данной задаче жадный алгоритм не дает полной оптимизации 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	26.11.2021, 11:50
	Catstail, Но ведь по любому для каждой точки приходится находить ближайшую, перебирая оставшиеся... 0

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	26.11.2021, 16:25
	Gdez, это и есть "жадный алгоритм". Он даст приемлемое решение, но не обеспечивает глобальной минимальности. 1