Программирование, т. 7

Курсовая работа

ты уже придумал как будешь реализовывать?

бтв на вики статья неплохая https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution

Да с программой проблем не будет офк, а вот пояснительная записка мозги поебет

если не ошибаюсь там сам алгоритм будет строк на 30

найти все пути от А до Б-> выбрать самый длинный -> пройти пониму маркируя вершины -> и тоже самое в обратном порядке

ниче не забыл?

Клевая курсовая ака задачка на 20 минут собеседования

найти все пути от А до Б-> выбрать самый длинный -> пройти пониму маркируя вершины -> и тоже самое в обратном порядке

бля это же изи

а прочитав описание нихуя не понял 

бля это же изи

а прочитав описание нихуя не понял 

Чета жиза

вы долбоебы это NP полная задача

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

смотрите ссылку на вики выше

а да, сори

за долбаеба - ответишь

upd: надо найти самый длинный путь A до B-> перейти на след вершину C-> маркануть ее -> найти cамый длинный путь от С до B и тд 

(ссылку не смотрел)

вы долбоебы это NP полная задача

И что?

Тебе нужно NP время чтобы алгоритм перепечатать?

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

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

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

По последним 2 постам в топике вы можете увидеть, кто здесь программист, а кто ебаный стажер

По последним 2 постам в топике вы можете увидеть, кто здесь программист, а кто ебаный стажер

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

 

upd: надо найти самый длинный путь A до B-> перейти на след вершину C-> маркануть ее -> найти cамый длинный путь от С до B и тд 

 

(ссылку не смотрел)

это ничего не меняет. ты найдешь самый длинный путь в одну сторону и всё. оптимального решения это не даст

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

Я думаю на наборе в десяток городов и двадцаток прямых рейсов задачу можно решить и простым перебором наплевав на NP время. 

А так это обычная задача коммивояжёра, только с условием направления движения запад->восток->запад.  

Собственно сравнение времени перебора и жадного алгоритма ветвей и границ для классической задачи коммивояжера.

Если бы это была бы моя курсовая, я бы занялся it science и нашел бы жадный алгоритм который лоялен к динамическому изменению весов ребер/числу вершин в процессе работы.

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

да, можно посчитать перебор если городов мало. но в задаче написано про города канады, то есть речь идет о тысячах городов

думаю нужно предоставить решение для большого количества городов (хотя бы 1к) и продемонстрировать его работу на небольшом количестве чтобы показать что он в принципе работает. это же курсач а не лаба какая-то

и на счет запад восток, в условии не сказано что каждый следующий город должен быть западнее/южнее предыдущего, так что можно хоть змейкой летать

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

Я забыл название уже терминов, я не имел в виду алгоритм кратчайшего пути говоря про это.

Я с самого начала понимал, что тут поиск гамильтоново цикла. Просто не так выразился.

Ладно, все таки неплохая задачка для курсовой

и на счет запад восток, в условии не сказано что каждый следующий город должен быть западнее/южнее предыдущего, так что можно хоть змейкой летать

Офк хоть змейкой, но эффективно.

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

Где 0 и 8 это один и тот же город, самый западный, 3 и 5, 7 и 2, 1 и 6 это тоже одни и те же города, а 4 это самый восточный.

Тогда задача будет о переходе из 0 в 8 по гамильтонову циклу, но мы будем посещать города 2 раза. А нам это нельзя по условию. Следовательно проходя до вершины под номером 4 мы должны удалять города из второй половины которые уже посетили. 

Нужно только найти алгоритм, который это не сломает.

из 0 в 1 будет не на восток а на северо-восток

здарова, гуманитарий

из 0 в 1 будет не на восток а на северо-восток

Какая разница, главное чтобы не на запад по условию.

Но вообще это хуевый алгоритм, решать задачу двумя гамильтоновыми путями, на восток и на запад с вычеркнутыми посещенными вершинами. Ибо мы можем уничтожить вершины которые позволят нам вернутся домой и задача будет якобы без решений, когда решения есть.

Ещё как вариант сделать инвертированно. Путь с запада на восток + путь с востока на запад. А затем перевернуть все дуги и сделать ещё раз задачу с конца, сперва для второй половины якобы а потом для первой.

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

Но опять же это будет жадный алгоритм с ловушкой, я уверен. Будет находить локальный минимум или отсутствие решений когда оно есть.