Обсуждение:Задача коммивояжера, ДП по подмножествам — различия между версиями
| Строка 5: | Строка 5: | ||
| − | : {{tick}} Пункт «Формулировка задачи» не нужен, то что в нём можно поместить в шапку статьи. | + | : {{tick | ticked=1}} Пункт «Формулировка задачи» не нужен, то что в нём можно поместить в шапку статьи. |
| − | : {{tick}} Сложность решения методом перебора перестановок посчитана неправильно — у тебя N! перестановок и N времени на подсчёт длины каждого пути. | + | : {{tick | ticked=1}} Сложность решения методом перебора перестановок посчитана неправильно — у тебя N! перестановок и N времени на подсчёт длины каждого пути. |
| − | : {{tick}} Используется то <tex> s </tex>, то <tex> S </tex> | + | : {{tick | ticked=1}} Используется то <tex> s </tex>, то <tex> S </tex> |
| − | : {{tick}} То, что должно быть под <tex> \min </tex> почему-то справа. Видимо, надо использовать \limits. | + | : {{tick | ticked=1}} То, что должно быть под <tex> \min </tex> почему-то справа. Видимо, надо использовать \limits. |
| − | : {{tick}} «т.е. mask - подмножество вершин исходного графа, которые осталось посетить» — непонятно, какие именно вершины в mask осталось посетить. В общем, строго напиши, что обозначает 0 и что — 1. | + | : {{tick | ticked=1}} «т.е. mask - подмножество вершин исходного графа, которые осталось посетить» — непонятно, какие именно вершины в mask осталось посетить. В общем, строго напиши, что обозначает 0 и что — 1. |
| − | : {{tick}} Мне кажется, у тебя неправильно задана динамика(или описание у неё неправильное). d[i=0][mask=0] — конечное состояние(как написано перед заданием динамики), а значение в нём у тебя задаётся равным нулю. И вообще у тебя текстовое описание и до и после описания динамики формулами, определись. | + | : {{tick | ticked=1}} Мне кажется, у тебя неправильно задана динамика(или описание у неё неправильное). d[i=0][mask=0] — конечное состояние(как написано перед заданием динамики), а значение в нём у тебя задаётся равным нулю. И вообще у тебя текстовое описание и до и после описания динамики формулами, определись. |
| − | : {{tick}} В псевдокоде здесь писать 2 ^ j — плохо, так как «^» — xor. Пиши с битовым сдвигом или хотя бы 2 ** j. | + | : {{tick | ticked=1}} В псевдокоде здесь писать 2 ^ j — плохо, так как «^» — xor. Пиши с битовым сдвигом или хотя бы 2 ** j. |
| − | : {{tick}} В псевдокоде d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);, а надо d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j] + вес ребра(не знаю как он у тебя там называется); | + | : {{tick | ticked=1}} В псевдокоде d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);, а надо d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j] + вес ребра(не знаю как он у тебя там называется); |
| − | : {{tick}} Писать inputData и writeData не обязательно. Лучше оформить в виде функции, которая принимает то что нужно для того, чтобы решать задачу и возвращает d[0][2 ** n - 1] | + | : {{tick | ticked=1}} Писать inputData и writeData не обязательно. Лучше оформить в виде функции, которая принимает то что нужно для того, чтобы решать задачу и возвращает d[0][2 ** n - 1] |
| − | : {{tick}} А ещё не очень понятно, почему весовая функция для рёбер обознается p. Я понимаю, w(weight) или e(edges) или ещё что-то, имеющее аналог в английском языке. | + | : {{tick | ticked=1}} А ещё не очень понятно, почему весовая функция для рёбер обознается p. Я понимаю, w(weight) или e(edges) или ещё что-то, имеющее аналог в английском языке. |
| + | --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:46, 2 декабря 2011 (MSK) | ||
Версия 00:46, 2 декабря 2011
- ☑ В конспекте написано что задача отностится к классу NP-полных, но не сказано что это такое. Объяснить кратко.
- ☑ Написать (псевдо)код.
- ☑ Оформить три условия dp[i][m] нормально, как динамику — то есть база и переход. Использовать теховские большие фигурные скобки(для условного присваивания)(как здесь Задача о перемножении матриц#Рекурсивное решение)
- ☑ дополнительные улучшения форматирования приветствуются --Дмитрий Герасимов
- ☑ Пункт «Формулировка задачи» не нужен, то что в нём можно поместить в шапку статьи.
- ☑ Сложность решения методом перебора перестановок посчитана неправильно — у тебя N! перестановок и N времени на подсчёт длины каждого пути.
- ☑ Используется то , то
- ☑ То, что должно быть под почему-то справа. Видимо, надо использовать \limits.
- ☑ «т.е. mask - подмножество вершин исходного графа, которые осталось посетить» — непонятно, какие именно вершины в mask осталось посетить. В общем, строго напиши, что обозначает 0 и что — 1.
- ☑ Мне кажется, у тебя неправильно задана динамика(или описание у неё неправильное). d[i=0][mask=0] — конечное состояние(как написано перед заданием динамики), а значение в нём у тебя задаётся равным нулю. И вообще у тебя текстовое описание и до и после описания динамики формулами, определись.
- ☑ В псевдокоде здесь писать 2 ^ j — плохо, так как «^» — xor. Пиши с битовым сдвигом или хотя бы 2 ** j.
- ☑ В псевдокоде d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);, а надо d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j] + вес ребра(не знаю как он у тебя там называется);
- ☑ Писать inputData и writeData не обязательно. Лучше оформить в виде функции, которая принимает то что нужно для того, чтобы решать задачу и возвращает d[0][2 ** n - 1]
- ☑ А ещё не очень понятно, почему весовая функция для рёбер обознается p. Я понимаю, w(weight) или e(edges) или ещё что-то, имеющее аналог в английском языке.
--Дмитрий Герасимов 00:46, 2 декабря 2011 (MSK)
