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

@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, это и есть "жадный алгоритм". Он даст приемлемое решение, но не обеспечивает глобальной минимальности.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

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

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

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

@Catstail Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,733 Записей в блоге: 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 Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,733 Записей в блоге: 14
	26.11.2021, 16:25
	Gdez, это и есть "жадный алгоритм". Он даст приемлемое решение, но не обеспечивает глобальной минимальности. 1