LINUX.ORG.RU
 

Алгоритмическая задача о красках.


0

0

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

Задача:

Есть поле, состоящее из 19 шестигранников, распологающихся в след форме: http://img155.imageshack.us/img155/2292/43405000.jpg

Есть 5 различных красок. Необходимо его раскрасить так, чтобы краски в соседних шестигранниках не совпадали. Центральный шестиугольник имеет другую, отличную от предложенных красок раскраску.

Краски: Краски "a", "b" и "c" - по 4 штуки каждой. Краски "d" и "e" - по 3 штуки.

Требуется найти произвольное (рандомное) решение.

P.S. Сколько не продумывал вариантов. Но самым быстрым оказался вариант полного перебора с записью в файл. А в рантайме просто вытаскивать из этого файла необходимую комбинацию. Но давольно много мегабайтов такой файл занимает, даже если отсеч одинаковые (через поворот, а точнее 5 поворотов) комбинации.


 ← 1 2 →
[#]  
KRoN73

Re: Алгоритмическая задача о красках.

man «Задача о раскраске карты» :)

...

Вообще-то, 4-х красок достаточно, чтобы раскрасить любую плоскую конфигурацию.

***** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от KRoN73 19.07.2009 15:58:28  

Re: Алгоритмическая задача о красках.

> Вообще-то, 4-х красок достаточно, чтобы раскрасить любую плоскую конфигурацию.

Задаче не в доказательстве существования решения. А в нахождении рандомного решения.

* ()
[#]  
www_linux_org_ru

Re: Алгоритмическая задача о красках.

> Но давольно много мегабайтов такой файл занимает, даже если отсеч одинаковые (через поворот, а точнее 5 поворотов) комбинации.

1. отсечь отражения х/=2

2. отсечь перестановки красок abc х/=6

3. отсечь перестановки красок de х/=2

или, альтернативно, забить на мегабайты.

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от www_linux_org_ru 19.07.2009 16:17:12  

Re: Алгоритмическая задача о красках.

> 1. отсечь отражения ... или, альтернативно, забить на мегабайты.

Файл все равно получается достаточно большой относительно решаемой задачи. В любом случае этим вариантом я пользовался давно порядка 6-8 лет назад. Все повороты были отброшены, файл ЕМНИП занимал более 50МБ.

> 1. отсечь отражения х/=2

поворотов может быть всего 6 (включая оригинал). x/=6

> 2. отсечь перестановки красок abc х/=6

а вот тут наоборот x/=4

abc, bac, cba, acb - всего 4 перестановки.

Предлагаю просто забыть, что есть такой вариант решения. Доп. ограничение: сохранять на диск ничего нельзя. Надо сгенерировать "на лету".

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 19.07.2009 16:11:26  
KRoN73

Re: Алгоритмическая задача о красках.

>Задаче не в доказательстве существования решения. А в нахождении рандомного решения.

Так в классическом решении задачи что тебе не нравится? Решение-то примитивное и не одну сотню лет известное. Это доказать его смогли лишь недавно.

Берёшь любую клетку (в твоём случае - ту, что уже предварительно окрашена) и закрашиваешь соседей, чередуя два цвета. Если число соседей нечётное, то во избежание совмещения цветов используется третий цвет. Всё :)

***** ()
[#]  

Re: Алгоритмическая задача о красках.

А рандомно выбирать можно из какого-то множества решений или именно из всех?

** ()
[#]  

Re: Алгоритмическая задача о красках.

А что если взять какое-то одно решение. Например такое: по внешнему периметру acabcbacabcb, по внутреннему (вокруг центра) - dedede (лично мне проще на это смотреть как на граф: в центры шестиугольников нарисовать вершины, и соеденить их соответственно тому как они соприкасаются друг с другом; тогда на концах любого ребра графа не должно быть одинаковых значений). К решению затем применять какие-то случайные трансформации, которые бы генерировали другие конфигурации. Правда тебе надо доказать, что существует последовательность трансформаций, такая, что применив её, ты можешь получить любую конфигурацию из множества допустимых конфигураций. Или более общно: для любых двух конфигураций из множества решений существует последовательность трансформаций, превращающая одну в другую. Или доказать обратное и искать другое вариант решения задачи. :-)

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 19.07.2009 16:33:54  
www_linux_org_ru

Re: Алгоритмическая задача о красках.

> поворотов может быть всего 6 (включая оригинал). x/=6

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

> abc, bac, cba, acb - всего 4 перестановки.

Чувак, ты похоже совсем не в теме. Перестановок 6=3! abc acb bac bca cab cba

Вывод: юзай 50МВ файл.

**** ()
[#]  
Waterlaz

Re: Алгоритмическая задача о красках.

А решение то простое:

нумеруешь клетки слева напрво и сверху вниз:

  1 2 3
 4 5 6 7
8 9.....
...

Легко доказать, что если первые n клеток раскрашены так, что удовлетворяют требованию соседства, то и n+1 - ую тоже можно так раскрасить.
Вот и раскрашивай их в таком порядке. Сперва первую в случайный цвет. 
Потом вторую из оставшихся. Потом 3-ю, 4-ю. Потом 5-ую случайно одним из цветов не совпадающих с 4, 1, 2. Потом 6-ую. итд...

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

** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от Waterlaz 19.07.2009 23:14:13  

Re: Алгоритмическая задача о красках.

Следуя твоему алгоритму, получаю:

  a d e
 b c a b
a d   c d
 b c e b
  a 

осталось е и с, которые некуда вставить.

*** ()
[#]  
gkrellm

Re: Алгоритмическая задача о красках.

1. Грамматика ни к чёрту. Тебя трудно воспринимать всерьёз.

2. Пойми в чём отличие грани от угла.

2. Геометрия задачи слишком специфична, чтобы искать красивое решение. Хотя стремление к лаконичности похвально и приветствуется.

4. Не знаю, чего тебе советуют в коментах, но перестановок красок 5!. И упрощение идет изменением алгоритма перебора во вложенных циклах, стартуя индексную переменную со значения, не меньшего текущего значения индексной переменной внешнего цикла. Лишь потом на полученные решения для 5 красок накладывается маска-условие того что три краски по 4, а две — по 3.

5. Ускорить алгоритм перебора можно, введя матрицу связности для графа карты и обходя в лоб уже её. Заодно решится более общая задача раскрашивания произвольной карты заданным числом красок.

Вердикт: школотоподобный неуч, приобщающийся к Истине. Что ж, успехов.

()
[#] Ответ на: Re: Алгоритмическая задача о красках. от www_linux_org_ru 19.07.2009 22:06:16  

Re: Алгоритмическая задача о красках.

> > abc, bac, cba, acb - всего 4 перестановки.

> Чувак, ты похоже совсем не в теме. Перестановок 6=3! abc acb bac bca cab cba

Да, извиняюсь. Что-то меня переклинило, про остальные 2 подстановки. Видимо мозг уже не работал, когда писал (у нас уже ночь была). Но тем не менее - это не желаемое решение.

> > поворотов может быть всего 6 (включая оригинал). x/=6

> Отражение *не может* быть заменено поворотом, если у тебя не все решения зеркально симметричные.

шесть поворотов по 30 градусов, в силу специфики фигуры. Что я не так понял?

> Waterlaz (*) (19.07.2009 23:14:13)

Такой вариант рассматривался. Он не гарантирует успешного нахождения решения. Хотя если луна будет в нужной фазе - то получим рандомное решение.

> 1. Грамматика ни к чёрту. Тебя трудно воспринимать всерьёз.

Да ну? Другие что-то не жалуются.

> 2. Пойми в чём отличие грани от угла.

Отличие прекрасно понимаю. А ты знаешь что количество углов равно количеству сторон (граней) ?

> 2. Геометрия задачи слишком специфична, чтобы искать красивое решение. Хотя стремление к лаконичности похвально и приветствуется.

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

> 4. Не знаю, чего тебе советуют в коментах, но перестановок красок 5!. И упрощение идет изменением алгоритма перебора во вложенных циклах, стартуя индексную переменную со значения, не меньшего текущего значения индексной переменной внешнего цикла. Лишь потом на полученные решения для 5 красок накладывается маска-условие того что три краски по 4, а две — по 3.

Единственное дельное замечание из твоего комментария. Но есть одно "но": самым большим тормозом будет как-раз проверка на валидность решения. А этим ты еще и уменьшаешь вероятность получения правильного решения. Может получиться так, что какой-то краски будет использовано 6 штук, или что 5ая краска задействована не будет вообще. Что в принципе математически допустимо. Читай первые комментарии KRoN73.

Диагноз: ЧСВ не позволяет нормально жить.

* ()
[#]  

Re: Алгоритмическая задача о красках.

>>Есть поле, состоящее из 19 шестигранников, распологающихся в след форме:

>шестигранников

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 3:06:30  
gkrellm

Re: Алгоритмическая задача о красках.

>>Да ну? Другие что-то не жалуются.

Ты что, носом быть тыкуемым приучен?

->Сколько не продумывал

->давольно

->отсеч

>>сторон (граней) ?

Epic doublefacepalmfail.

>>Но есть одно "но": самым большим тормозом будет как-раз проверка на валидность решения.

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

Экспертное заключение: irq упорот и борз больше достаточного для ментального прогресса.

>>Диагноз: ЧСВ не позволяет нормально жить.

Это у тебя возрастное. Пройдет.

()
[#] Ответ на: Re: Алгоритмическая задача о красках. от smh 19.07.2009 23:56:57  
beastie

Re: Алгоритмическая задача о красках.

а что, если изменить алгоритм Waterlaz'а таким образом, что если законичились краски -- возвращаемся на n шагов назад, перекрашиваем. если красок опять не хватило -- возвращаемся на n + 1 и т.д.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от beastie 20.07.2009 5:27:55  
gkrellm

Re: Алгоритмическая задача о красках.

>>а что, если изменить алгоритм Waterlaz'а таким образом, что если законичились краски -- возвращаемся на n шагов назад, перекрашиваем. если красок опять не хватило -- возвращаемся на n + 1 и т.д.

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

()
[#] Ответ на: Re: Алгоритмическая задача о красках. от gkrellm 20.07.2009 4:42:35  

Re: Алгоритмическая задача о красках.

> Ты что, носом быть тыкуемым приучен?

>->Сколько не продумывал

>->давольно

>->отсеч

>>>сторон (граней) ?

>Epic doublefacepalmfail.

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

man _правила_русского_языка_

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

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

> Экспертное заключение: irq упорот и борз больше достаточного для ментального прогресса. Это у тебя возрастное. Пройдет.

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

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 6:27:33  

Re: Алгоритмическая задача о красках.

А вообще лучше бы что-то по делу предложил, чем приближено кубировать сферических коней в вакууме.

* ()
[#]  
arsi

Re: Алгоритмическая задача о красках.

   a b a
  b c d b
 a d x a c
  e b c e
   c e d

я правильно понял условие?

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 14:02:12  
arsi

Re: Алгоритмическая задача о красках.

из меня плохой сказочник =) так что просто приведу пример решения
(на перле; надеюсь, проблем с пониманием кода не возникнет):

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#!/usr/bin/perl

use strict;
use warnings 'all';

my @colors = qw(a b c d e);
my @count = (4, 4, 4, 3, 3);

my @rel = ([], [0], [1], [0], [0,1,3], [1,2,4], [2,5], [3], [3,4,7], [], [5,6], [6,10],
           [7,8], [8,12], [10,13], [10,11,14], [12,13], [13,14,16], [14,15,17]);

my @cells = ('x') x 19;

sub iterate {
    my $cell = shift || 0;
    if ($cell == 19) {
        printf "%4s%2s%2s\n%3s%2s%2s%2s\n%2s%2s%2s%2s%2s\n%3s%2s%2s%2s\n%4s%2s%2s\n\n",
               @cells[0..2], @cells[3..6], @cells[7..11], @cells[12..15], @cells[16..18];
        exit;
    } elsif ($cell == 9) {
        iterate($cell + 1);
    } else {
        L:for my $i (0..$#colors) {
            next unless $count[$i];
            $cells[$cell] = $colors[$i];
            do { next L if $cells[$_] eq $cells[$cell] } for @{$rel[$cell]};
            --$count[$i];
            iterate($cell + 1);
            ++$count[$i];
        }
    }
}

iterate;

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

можно спрашивать :)

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от arsi 20.07.2009 14:47:32  

Re: Алгоритмическая задача о красках.

> можно спрашивать :)

в перле не силен, спрашиваю =)

без комментариев разобраться тяжело какой алгоритм. И так как все-таки в перле не силен, уточню: функция iterate ищет первое правильное решение или все-таки случайное.

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 19.07.2009 16:33:54  
Manhunt

Re: Алгоритмическая задача о красках.

> Файл все равно получается достаточно большой относительно решаемой задачи. В любом случае этим вариантом я пользовался давно порядка 6-8 лет назад. Все повороты были отброшены, файл ЕМНИП занимал более 50МБ.

Я не стал отбрасывать повороты и отражения, а отбросил только перестановки цветов (группы a-b-c и d-e). Получилось 784565 разных раскрасок. Каждая из них легко кодируется 18-ти разрядным числом в 5-ричной системе счисления, то есть 6-ю байтами. Размер бинарного массива будет 5*784565 байт, то есть менее 5 МБ. Ня?

=============================

Запуск на Core2 занял около 20 минут.

#include <algorithm>
#include <string>
#include <iostream>

class Coloring
{
	char c[18];

//			0		1		2
//		3		4		5		6
//	7		8				9		10
//		11		12		13		14
//			15		16		17

public:

	void Reset()
	{
		c[ 0] = 'a';
		c[ 1] = 'a';
		c[ 2] = 'a';
		c[ 3] = 'a';
		c[ 4] = 'b';
		c[ 5] = 'b';
		c[ 6] = 'b';
		c[ 7] = 'b';
		c[ 8] = 'c';
		c[ 9] = 'c';
		c[10] = 'c';
		c[11] = 'c';
		c[12] = 'd';
		c[13] = 'd';
		c[14] = 'd';
		c[15] = 'e';
		c[16] = 'e';
		c[17] = 'e';
	}

	bool Next()
	{
		return std::next_permutation(c, c + sizeof(c));
	}

	bool IsMonotoneABC() const
	{
		char max = 'a' - 1;
		for(int i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'a' || x == 'b' || x == 'c')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsMonotoneDE() const
	{
		char max = 'd' - 1;
		for(int i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'd' || x == 'e')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsGood() const
	{
		return
			c[ 0] != c[ 1] && c[ 0] != c[ 3] && c[ 0] != c[ 4] &&
			c[ 1] != c[ 2] && c[ 1] != c[ 4] && c[ 1] != c[ 5] &&
			c[ 2] != c[ 5] && c[ 2] != c[ 6] &&
			c[ 3] != c[ 4] && c[ 3] != c[ 7] && c[ 3] != c[ 8] &&
			c[ 4] != c[ 5] && c[ 4] != c[ 8] &&
			c[ 5] != c[ 6] && c[ 5] != c[ 9] &&
			c[ 6] != c[ 9] && c[ 6] != c[10] &&
			c[ 7] != c[ 8] && c[ 7] != c[11] &&
			c[ 8] != c[11] && c[ 8] != c[12] &&
			c[ 9] != c[10] && c[ 9] != c[13] && c[ 9] != c[14] &&
			c[10] != c[14] &&
			c[11] != c[12] && c[11] != c[15] &&
			c[12] != c[13] && c[12] != c[15] && c[12] != c[16] &&
			c[13] != c[14] && c[13] != c[16] && c[13] != c[17] &&
			c[14] != c[17] &&
			c[15] != c[16] &&
			c[16] != c[17];
	}

	std::string ToString() const
	{
		return std::string(c, c + sizeof(c));
	}
};

int main()
{
	Coloring c;
	c.Reset();
	while(c.Next()) if(c.IsGood()) if(c.IsMonotoneABC()) if(c.IsMonotoneDE())
	{
		std::cout << c.ToString() << std::endl;
	}
}

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 15:24:30  
arsi

Re: Алгоритмическая задача о красках.

первое. если убрать «exit», будет искать/печатать все.

зы: могу на С дать, но он ещё сложнее ;)

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от Manhunt 20.07.2009 15:30:02  
Manhunt

Re: Алгоритмическая задача о красках.

> Запуск на Core2 занял около 20 минут.

Ыыыы! Я идиот. Если собрать с -O3, запуск занимает 3 минуты.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от arsi 20.07.2009 15:31:16  

Re: Алгоритмическая задача о красках.

> могу на С дать, но он ещё сложнее ;)

сложнее - не страшно, главное что понятнее будет. Но дело не в решении их может быть чуть меньше чем бесконечность. Лучше объясни твой алгоритм, если тебе не трудно. =)

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от Manhunt 20.07.2009 15:30:02  

Re: Алгоритмическая задача о красках.

> Запуск на Core2 занял около 20 минут.

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

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 15:41:02  

Re: Алгоритмическая задача о красках.

а как я понимаю там просто перебор и в произвольности решения разговора нет. 
Я конечно, понимаю, что можно сделать так:

int r = random() / (RAND_MAX) * SOLVE_AMOUNT;
for (int i=0; i < r; ++i)
{
 seek_solution;
 if (i == r) break; // дошли до нужного решения
}

Но хочется чего-то красивого и изящного. =)

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 15:24:30  
Manhunt

Re: Алгоритмическая задача о красках.

> без комментариев разобраться тяжело какой алгоритм

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

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 15:46:04  
Manhunt

Re: Алгоритмическая задача о красках.

> Но хочется чего-то красивого и изящного.

На целевой машине нет лишних 5 Мб оперативы? Если есть, то можно на этапе инициализации по алгоритму "от arsi" заполнять массив, а затем делать из него моментальную выборку. Думаю, при аккуратной имплементации его алгоритм на современном проце заполнит массив за несколько секунд.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от Manhunt 20.07.2009 15:54:36  
Manhunt

Re: Алгоритмическая задача о красках.

Или хранить в исполнимом файле уже готовый массив - загрузка моментальная, но бинарник несколько распухает.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 15:41:02  
Manhunt

Re: Алгоритмическая задача о красках.

> Но хочется составить алгоритм нахождения рандомного решения без записи и чтения из доп. файлов

5 Мб не трудно запихнуть в массив на этапе компиляции.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от Manhunt 20.07.2009 15:54:36  
Manhunt

Re: Алгоритмическая задача о красках.

> Думаю, при аккуратной имплементации его алгоритм на современном проце заполнит массив за несколько секунд.

irq, если хочешь, могу даже заимплементить на Си (или на C++ - мне все равно). Условие - твоя программа, использующая этот код, публикуется под GPL.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 15:38:12  
arsi

Re: Алгоритмическая задача о красках.

ок, вот на сях.
ищет _рандомное_ решение.

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#include <stdio.h>                                     
#include <stdlib.h>                                    
#include <time.h>                                      

static const char colors[5] = "abcde";
static int left[5] = { 4, 4, 4, 3, 3 };
static char cells[19];                 
static const int rel[19][4] = {        
    {0}, {-1}, {-1},                   
    {-3}, {-4, -3, -1}, {-4, -3, -1}, {-4, -1},
    {-4}, {-5, -4, -1}, {0}, {-5, -4}, {-5, -1},
    {-5, -4}, {-5, -1}, {-4, -1}, {-5, -4, -1}, 
    {-4, -3}, {-4, -3, -1}, {-4, -3, -1}        
};                                              

static void randomize(char *p) {
    int n = 5, mask = 0;        
    while (n) {                 
        int v = 0, r = 1 + rand() % n--;
        for (; r; ++v)                  
            if ((mask & (1 << v)) == 0) 
                --r;                    
        *p++ = --v;                     
        mask |= 1 << v;                 
    }                                   
}                                       

static int iterate(int i) {
    int n = 5;             
    char *p = &cells[i];   
    const int *r;          
    char inx[5];           
                           
    if (i == 19) {         
        printf("  %c %c %c\n", cells[0], cells[1], cells[2]);
        printf(" %c %c %c %c\n", cells[3], cells[4], cells[5], cells[6]);
        printf("%c %c x %c %c\n", cells[7], cells[8], cells[10], cells[11]);
        printf(" %c %c %c %c\n", cells[12], cells[13], cells[14], cells[15]);
        printf("  %c %c %c\n\n", cells[16], cells[17], cells[18]);
        return 1;
    }

    if (i == 9)
        return iterate(i + 1);

    randomize(inx);
    while (n--) {
        int c = inx[n];
        int ok = 1;
        if (!left[c])
            continue;
        *p = colors[c];
        for (r = rel[i]; *r && ok; ++r)
            if (*p == p[*r])
                ok = 0;
        if (!ok)
            continue;
        --left[c];
        ok = iterate(i + 1);
        ++left[c];
        if (ok)
            return 1;
    }
    return 0;
}

int main() {
    srand(time(NULL));
    cells[9] = 'x';
    return !iterate(0);
}
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

а по поводу объяснить… ой тяжело мне это ^_^'
посмотри на код, если не поймёшь, попробую как-нибудь объяснить =)

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от Manhunt 20.07.2009 15:57:21  

Re: Алгоритмическая задача о красках.

> Или хранить в исполнимом файле уже готовый массив - загрузка моментальная, но бинарник несколько распухает.

Разкмеется можно, я этого не отрицаю. И считаю этот вариант одним из лучших. Но: <Немного оффтопа> В старые времена спектрумов (когда я, собственно говоря, знакомился с "умной" техникой) Очень ценолось и широко использовалась оптимизация на уровне математики, мат. модели. Если можно было генерировать данные "на лету" а не считывать их из большого файла, то выбиралось первое. Потом оптимизировался алгоритм. и в итоге все работало сравнительно быстро. Я, конечно, понимаю что: "железо сейчас быстрее...", "такая оптимизация не нужна..", и т.д. По большей части пунктов да, я согласен. Но чем плохо немного пошевелить мозгами и придумать такой алгоритм, чтобы нчего не хранить и не слишеом долго ждать. </оффтоп>

Очень интесует один вопрос, относительно рекурсивного метода:

Как понять, что дальше заполнить карту нельзя? Когда остановить рекурсию и на сколько шагов назад вернуться, если нельзя оставшимися цветами дальше заполнять карту?

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от arsi 20.07.2009 16:15:55  

Re: Алгоритмическая задача о красках.

> а по поводу объяснить… ой тяжело мне это ^_^' посмотри на код, если не поймёшь, попробую как-нибудь объяснить =)

Ок, посмотрю проверю, что не пойму - напишу в тред. Часиков через 12...

* ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от irq 20.07.2009 16:20:29  
arsi

Re: Алгоритмическая задача о красках.

> Как понять, что дальше заполнить карту нельзя? Когда остановить рекурсию и на сколько шагов назад вернуться, если нельзя оставшимися цветами дальше заполнять карту?

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

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от arsi 20.07.2009 14:47:32  

Re: Алгоритмическая задача о красках.

> (на перле; надеюсь, проблем с пониманием кода не возникнет):

Ну, рекурсивно перебрать все возможные варианты - это наверное не совсем The Right Thing. Хотя, видимо, тут ничего лучше не придумать. Можно как вариант один раз сгенерировать дерево всех решений и затем ходить по нему рандомно.

*** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от smh 20.07.2009 18:14:58  
arsi

Re: Алгоритмическая задача о красках.

> Можно как вариант один раз сгенерировать дерево всех решений и затем ходить по нему рандомно.

9414780 вариантов (это без отсеивания похожих) как-то тяжело представить в виде дерева ^_^'

кроме того, при таком количестве вариантов перебор будет не таким долгим. установил вот ради интереса счётчик в начало итерационной функции — количество вызовов в основном около 20…22 (при минимуме в 20), но часто доходит до 50, и редко — до 500, а ≥1000 вообще не замечал (хоть и не исключаю такую возможность). так что ничего страшного ;)

зы: при 268 вызовах: real 0m0.004s // user 0m0.000s // sys 0m0.000s ^_^

**** ()
[#] Ответ на: Re: Алгоритмическая задача о красках. от arsi 20.07.2009 18:44:56  

Re: Алгоритмическая задача о красках.

> 9414780 вариантов (это без отсеивания похожих) как-то тяжело представить в виде дерева ^_^'

Ну, это да. Хотя там должно быть много общих веток. В любом случае будет меньше файла в 50 мегабайт. :-)

> кроме того, при таком количестве вариантов перебор будет не таким долгим.

Ну раз перебор не долог, то может и нормально.

*** ()
[#]  

Re: Алгоритмическая задача о красках.

эскиз.

#define COLOR1 0x01
#define COLOR2 0x02
#define COLOR3 0x04
#define COLOR4 0x08
#define COLOR5 0x10

n=5;
m[]={3,4,5,4,3};
shift[]={-1,-1,-1,0,0};


for(i=0;i<n;i++)
for(j=0;j<m[i];j++)
{
if(i>0)
{
jj=j+shift[i];
if(jj>0) neighbours|=m[i-1][jj]
jj=j+shift[i]+1;
if(jj>0) neighbours|=m[i-1][jj]
}
if(j>0) neighbours|=m[i][j-1]

m[i][j]=random_excluding(neighbours);
}

вопросы?

** ()
 ← 1 2 →
Development