Программирование[8]

Это вроде задача коммивояжера и сложность факториальная

 

 

Это вроде гамильтонов цикл и сложность квадратичная

 

 

 

Это вроде гамильтонов цикл и сложность квадратичная

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

 

заткнитесь

 

Это вроде гамильтонов цикл и сложность квадратичная

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

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

Или я что-то путаю?

 

Это вроде гамильтонов цикл и сложность квадратичная

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

 

Ну так епта гамильтонов цикл с минимальным весом

 

Это вроде гамильтонов цикл и сложность квадратичная

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

 

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

может окошко откроем, а то душновато

Окошко откроем только чтобы выйти так что стоять руки за голову

 

 

Это вроде гамильтонов цикл и сложность квадратичная

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

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

Или я что-то путаю?

 

 

 

 

Это вроде гамильтонов цикл и сложность квадратичная

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

 

Ну так епта гамильтонов цикл с минимальным весом

 

ребят, у вас задача даже стоит в вычислении сложности алгоритма

вас не смущает, что поиск МИНИМАЛЬНОГО гамильтонова цикла внезапно намного сложнее?

их (n-1)! штук в графе, внезапно?

вон даже блять алгоритм вам нагуглил

https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_нахождения_Гамильтонова_цикла_в_условиях_теорем_Дирака_и_Оре

 

O(n^2) как я и ожидал

 

но такую мелочь как н квадрат при описании сложности коммивояжера даже не пишет никто, факториал всех уроет

ебать админы душат

Не понял, почему циклов с наименьшим весом (n - 1)! ?

всего циклов столько же, наименьший один офк.

написал немного хуёво мб

Ребят, как вы быстро перемещаете каретку в редакторе?

 

Вот просто смотрю какие лекции, там хуяк хуяк все быстро переводят. 

 

Я блять знаю что с зажатым контролом в IDEA можно по словам конструкциям перемещать, но это все равно долго.

Хочу натренироваться, чтобы придя на работу не показаться бабкой эникейщицей, которая мышкой всё тычет.

юзаю стрелки, стрелки + ctrl, home / end, home / end + ctrl

бтв это последнее задание из 10 в тесте xored

Чет я все равно не понял чем отличается кратчайший гамильтоновский цикл и коммивояжер

ничем

Ребят, как вы быстро перемещаете каретку в редакторе?

 

Вот просто смотрю какие лекции, там хуяк хуяк все быстро переводят. 

 

Я блять знаю что с зажатым контролом в IDEA можно по словам конструкциям перемещать, но это все равно долго.

Хочу натренироваться, чтобы придя на работу не показаться бабкой эникейщицей, которая мышкой всё тычет.

 

h j k l

w W e E

$ ^

gg G

 

и всё такое прочее

 

Это вроде гамильтонов цикл и сложность квадратичная

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

 

из википедии по коммивояжеру: "Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. "

 

Ребят, как вы быстро перемещаете каретку в редакторе?

 

Вот просто смотрю какие лекции, там хуяк хуяк все быстро переводят. 

 

Я блять знаю что с зажатым контролом в IDEA можно по словам конструкциям перемещать, но это все равно долго.

Хочу натренироваться, чтобы придя на работу не показаться бабкой эникейщицей, которая мышкой всё тычет.

 

h j k l

w W e E

$ ^

gg G

 

и всё такое прочее

 

расшифруй

блять, вы рофлите что ли

 

коммивояжер - выбор минимального гамильтонова цикла - сложность (n-1)!

просто гамильтонов цикл построить - сложность n^2

 

 

задача в определении сложности нахождения такого пути

что вы пытаетесь родить?

 

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

слова минимальный и сложность видно, или мне красным кружочком выделить?

блять, вы рофлите что ли

 

коммивояжер - выбор минимального гамильтонова цикла - сложность (n-1)!

просто гамильтонов цикл построить - сложность n^2

 

 

задача в определении сложности на

что вы пытаетесь родить?

 

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

слова минимальный и сложность видно, или мне красным кружочком выделить?

выдохни и перечитай спокойно то на что ты бомбишь

 

никто не говорит что указанная задачка это задачка поиска первого попавшегося г. цикла

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

собственно ты сам написал что это "ничем" не отличается. че у тебя бомбит - непонятно

 

пс:

ты привел алгоритм "в условиях теорем Дирака и Оре"

что будет с вычислением по данному алгоритму если граф не соответствует им? не требует ли это условие дополнительной проверки за O(..) ?

Изменено 10 апреля 2019 пользователем Just.Doit