Комбинаторика

Xenia1996 · Сообщение **Xenia1996** » 06 июн 2011, 09:34

Сколькими способами можно, не отрывая карандаш от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4 на 4?

Один из способов изображён тут:
[url=http://problems.ru/view_problem_details_new.php?id=103753]http://problems.ru/view_problem_details_new.php?id=103753[/url]

Если принять нижнюю левую точку (из 16) за ориго (начало координат), то сей способ выглядит так:
(0, 3) - (3, 3) - (3, 0) - (-1, 0) - (2, 3) - (2, 0) - (0, 2)

Я придумала ещё два принципиально иных (в смысле, при повороте или перевороте они не переходят друг в друга) способа:

(0, 0) - (0, 4) - (4, 0) - (1, 0) - (4, 3) - (1, 3) - (1, 1)
(1, 0) - (1, 3) - (4, 0) - (0, 0) - (0, 3) - (4, 3) - (2, 1)

А как узнать, сколько всего способов?

Equinoxe · Сообщение **Equinoxe** » 06 июн 2011, 11:26

Xenia1996 писал(а):Source of the post
Сколькими способами можно, не отрывая карандаш от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4 на 4?

Один из способов изображён тут:
[url=http://problems.ru/view_problem_details_new.php?id=103753]http://problems.ru/view_problem_details_new.php?id=103753[/url]

Если принять нижнюю левую точку (из 16) за ориго (начало координат), то сей способ выглядит так:
(0, 3) - (3, 3) - (3, 0) - (-1, 0) - (2, 3) - (2, 0) - (0, 2)

Я придумала ещё два принципиально иных (в смысле, при повороте или перевороте они не переходят друг в друга) способа:

(0, 0) - (0, 4) - (4, 0) - (1, 0) - (4, 3) - (1, 3) - (1, 1)
(1, 0) - (1, 3) - (4, 0) - (0, 0) - (0, 3) - (4, 3) - (2, 1)

А как узнать, сколько всего способов?

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

Xenia1996 · Сообщение **Xenia1996** » 06 июн 2011, 18:39

Equinoxe писал(а):Source of the post
Вообще говоря, бесконечное кол-во. Иначе же Вы считаете различными способы, у которых различен порядок обхода точек. Таким образом, эта задача о кол-ве минимальных гамильтоновых путей в графе, сомневаюсь, что она разрешима без перебора.

А программку для гамильтоновых путей не желаете состряпать?

vicvolf · Сообщение **vicvolf** » 07 июн 2011, 06:35

Сначала о существовании Гамильтонова пути в графе, так как он не всегда существует:
[url=http://ru.wikipedia.org/wiki/%C3%E0%EC%E8%...E2_%EF%F3%F2%FC]http://ru.wikipedia.org/wiki/%C3%E0%EC%E8%...E2_%EF%F3%F2%FC[/url]
А теперь о NP-полноте задачи :
[url=http://neerc.ifmo.ru/mediawiki/index.php/N...%84%D0%B0%D1%85]http://neerc.ifmo.ru/mediawiki/index.php/N...%84%D0%B0%D1%85[/url]
Это означает, что действительно задача решается только полным перебором!
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.

Equinoxe · Сообщение **Equinoxe** » 07 июн 2011, 10:53

vicvolf писал(а):Source of the post
Сначала о существовании Гамильтонова пути в графе, так как он не всегда существует:
[url=http://ru.wikipedia.org/wiki/%C3%E0%EC%E8%...E2_%EF%F3%F2%FC]http://ru.wikipedia.org/wiki/%C3%E0%EC%E8%...E2_%EF%F3%F2%FC[/url]
А теперь о NP-полноте задачи :
[url=http://neerc.ifmo.ru/mediawiki/index.php/N...%84%D0%B0%D1%85]http://neerc.ifmo.ru/mediawiki/index.php/N...%84%D0%B0%D1%85[/url]
Это означает, что действительно задача решается только полным перебором!
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.

Совершенно верно!

Pavlovsky · Сообщение **Pavlovsky** » 07 июн 2011, 12:33

Не понял. Как вы хотите к этой задаче прикрутить гамильтоновы пути? Всяко попробовал, фигня получается.

Equinoxe · Сообщение **Equinoxe** » 07 июн 2011, 13:27

Pavlovsky писал(а):Source of the post
Не понял. Как вы хотите к этой задаче прикрутить гамильтоновы пути? Всяко попробовал, фигня получается.

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

Кстати, Виктор-таки не прав, сводя задачку к классу NP-полных. Решив одну NP-полную за полином, можно решить и все остальные, вот только здесь граф имеет специальный вид, а значит задачка может свестись, но не факт, что станет.

Pavlovsky · Сообщение **Pavlovsky** » 07 июн 2011, 13:36

Не сами гамильтоновы, а кол-во минимальных.

И все равно у меня не получается.

Получается пока фигня.
1)Составить множество всех отрезков. С учетом вспомогательных точек. Учитывая наклонные отрезки. Причем не обязательно под углом 45 градусов.
2) Для каждого отрезка определить множество покрываемых точек.
3) Для каждого отрезка определить множество отрезков у которых есть общая конечная точка с данным отрезком.
4) построить все цепочки из отрезков состоящие из 6 отрезков.
5) Выбрать из них те которые покрывают все точки.

Боюсь для такого лобового решения потребуется суперкомпьютер.

Equinoxe · Сообщение **Equinoxe** » 07 июн 2011, 13:48

Pavlovsky писал(а):Source of the post
Не сами гамильтоновы, а кол-во минимальных.

И все равно у меня не получается.

Получается пока фигня.
1)Составить множество всех отрезков. С учетом вспомогательных точек. Учитывая наклонные отрезки. Причем не обязательно под углом 45 градусов.
2) Для каждого отрезка определить множество покрываемых точек.
3) Для каждого отрезка определить множество отрезков у которых есть общая конечная точка с данным отрезком.
4) построить все цепочки из отрезков состоящие из 6 отрезков.
5) Выбрать из них те которые покрывают все точки.

Боюсь для такого лобового решения потребуется суперкомпьютер.

Не, это Вы не совсем правы. Это, конечно, не совсем гамильтонов путь, но идея такая (по крайней мере исходную задачу она решает):
Пусть у нас зафиксирована маска обработанных точек и две точки, через которые проходит последний отрезок. Мы выбираем следующую точку из 16, которая будет обработана, и точку, направляющую отрезок, (по кол-ву прямых, т.е. это будет 0, 1 или 2). При этом в маску заносим только ту точку, которую выбрали (неважно, берёт ли отрезок до неё кого-то ещё, если только это не вторая точка, направляющая отрезок. Если отрезок берёт ещё кого-то, то путь, на которым мы сейчас, окажется слишком длинным, либо просто другим, а правильный обязательно переберётся). Как-то так

Перебирать придется именно две точки, т.к. не все точки, в которых мы будем поворачивать, находятся в этих 16-ти

Xenia1996 · Сообщение **Xenia1996** » 16 сен 2012, 09:21

Xenia1996 писал(а):Source of the post
Сколькими способами можно, не отрывая карандаш от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4 на 4?

Один из способов изображён тут:
[url=http://problems.ru/view_problem_details_new.php?id=103753]http://problems.ru/view_problem_details_new.php?id=103753[/url]

Если принять нижнюю левую точку (из 16) за ориго (начало координат), то сей способ выглядит так:
(0, 3) - (3, 3) - (3, 0) - (-1, 0) - (2, 3) - (2, 0) - (0, 2)

Я придумала ещё два принципиально иных (в смысле, при повороте или перевороте они не переходят друг в друга) способа:

(0, 0) - (0, 4) - (4, 0) - (1, 0) - (4, 3) - (1, 3) - (1, 1)
(1, 0) - (1, 3) - (4, 0) - (0, 0) - (0, 3) - (4, 3) - (2, 1)

А как узнать, сколько всего способов?

Придумала ещё один способ:

(3, 0) - (0, 0) - (0, 4) - (3, 1) - (3, 4) - (0, 1) - (3, 1)

yourdomain.com