Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
 Re: Задача оптимизации  [new]
exp98
Member

Откуда:
Сообщений: 3206
Если все нужны, тогда и циклы нужны, и комбинации циклов. А так да, алгоритмов дофига, и зачем было здесь спрашивать?
15 окт 21, 17:03    [22384279]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54798
Имя пользователя1
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.

Тогда простая рекурсия. Но она зациклится есть есть хоть одно кольцо.
16 окт 21, 13:56    [22384556]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
Имя пользователя1
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.


"всех" путей может оказаться бесконечно много.
16 окт 21, 16:01    [22384585]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
exp98
Member

Откуда:
Сообщений: 3206
Если хороводы кругами не не накручивать, бесконечностей не будет.
16 окт 21, 22:21    [22384636]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
exp98
Если хороводы кругами не не накручивать, бесконечностей не будет.


Тогда в задаче следует указать "не накручивая хороводы". Иначе непонятно будет чего хотят.
17 окт 21, 00:09    [22384666]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
Сделал примерно так:
Поиск в глубину запоминает альтернативные вершины для продолжения поиска в стеке.
При прохождении вершины в ней запоминается глубина стека.
На каждом шаге сначала проверяем это значение для новой вершины - В.
Если вершину не посещали - запоминаем глубину и продолжаем.
Иначе просматриваем все вершины и заменяем значение в них на мин(В, значение вершины) (**)
И специальные значения если через вершину (не) проходит путь ведущий к выходу.

Проблематично как мне видится действие (**).
Просмотр всех N вершин в худшем случае выполнится N раз. В итоге O(N^2)
Можно ли сделать быстрее?
18 окт 21, 09:12    [22384882]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
В коде нагляднее.

+

void OptimizeCode(int startNode)
{
	const int MATCH_TRACE = -1;
	const int IMPASSE_TRACE = -2;

	var tracemap = new int[_codeSize];
	int branch = 1;
	Stack<int> stack = null;

	int node = startNode;
	while (node < _codeSize)
	{
		int resolution = tracemap[node];
		if (resolution != 0)
		{
			if (resolution == branch)
				resolution = IMPASSE_TRACE;
			else if (IMPASSE_TRACE != resolution)
				branch = resolution;
		}
		else
		{
			tracemap[node] = branch;
			var inst = _code[node];
			switch (inst.OpCode)
			{
				case OPCODE_EXIT:
					resolution = branch = MATCH_TRACE;
					break;

				case OPCODE_HALT:
					resolution = IMPASSE_TRACE;
					break;
					
				case OPCODE_JUMP:
					node = target;
					continue;

				case OPCODE_SPLIT:
					if (stack == null)
						stack = new Stack<int>();
					stack.Push(inst.Target);
					branch = 1 + stack.Count;
					node += 1;
					continue;

				default:
					node += 1;
					continue;
			}
		}
		for (int i = tracemap.Length; --i >= 0;)
			if (tracemap[i] != 0 && branch <= tracemap[i])
				tracemap[i] = resolution;
		if (stack == null || stack.Count == 0)
			break;
		branch = stack.Count;
		node = stack.Pop();
	}
	// Here more ....
	
}

18 окт 21, 09:25    [22384885]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

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

в вашем случае он выполняется за O(N)
выполняется он максимум в 4 цикла, каждый из которых имеет асимптотику O(N)

1 цикл - ищите все переходы в ассоциативный массив <куда, откуда>
2 цикл - на старте помещаете в стек\очередь все результатные состояния и с помощью ассоциативного массива из первого цикла "обжигаете" пока стек не исчезнет, на выходе должны получиться "обожжённые пути"
3 цикл : из "обожённых" путей со второго цикла, нужно составить ассоциативный массив <откуда, куда> (его можно заполнить и во втором цикле)
4 цикл фактически тот же алгоритм что и во 2-м, но уже с использованием мапы<откуда, куда> от точек старта

PS: множества <куда, откуда> и <откуда, куда> естественно MultiMap (т.е. позволяют хранить несколько ключей)
18 окт 21, 10:15    [22384901]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

Для начала вы описываете здесь какой-то "отжигной" алоритм, но не алгоритм Бржозовского. Или я чего-то не вижу?

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


Уже это уже противоречит вашему утверждению про "всего 4 цикла".

Ну и в заключениу к вашему "отжигному" алгоритму - достижимые конечные состояния нужно сначала найти. Это 5 цикл O(N)
18 окт 21, 11:23    [22384938]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

про Алгоритм Бржозовского - применим для НКА и ДКА.
Из вики про КА
При работе на вход КА поступают последовательно входные воздействия, а на выходе КА формирует выходные сигналы.

В моей задаче нету входного сигнала следователно это не КА, следовательно методы для ДКА и НКА не применимы.
18 окт 21, 11:47    [22384947]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan)
_дух_,
вот вы упёртый


вы можете вести диалог на уровне, без оскорблений и перехода на личности?
18 окт 21, 12:34    [22384977]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

есть такой анекдот

+
автор
Задача I
Пусть у нас есть пустой чайник, кран с водой, спички, газовая конфорка.
Перед физиком и математиком ставят задачу вскипятить воду.
Действуют они одинаково.
1. Наливают воду в чайник.
2. Зажигают конфорку.
3. Ставят чайник на огонь и ждут, пока закипит.

Модифицируем Задачу I в Задачу II.
У нас уже есть чайник, наполненный водой и зажженная конфорка. Цель та же: вскипятить воду.

Физик ставит чайник на огонь и ждет, пока вода закипит.

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


Доказывается применимость очень просто, вот давайте сделаем как математики
у вас есть набор путей <откуда, куда>

а давай туда условие перехода добавим инкрементально (1, 2, 3 и т.д), т.е. на каждый переход у нас получится единственное неповторимое условие

и что мы увидим? КА
причём, ДКА, так как условия переходов у нас уникальные

а дальше что делать? - мы знаем ...

теперь по асимптотике, говорится, что алгоритм может быть экспоненциальным, но в самом алгоритме мы видим только циклы по количеству элементов O(N). Экспоненциальность получается в subset construction, при преобразовании
из НКА в ДКА. Но у нас уже ДКА, следовательно количество элементов может только уменьшаться!!!
следовательно алгоритм O(N) для нашего случая

Всё просто?
18 окт 21, 13:20    [22385006]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

А есть ещё поговорка - если у бабушки есть член то он уже дедушка.
Да, как вы написали сделать можно, но это как бы сказать -странно- привести задачу к общему случаю для того что бы реализовать решение для частного случая. И третий пункт задачи минимизации ДКА нам не нужен. Ну да бог с ним, а вот алгоритм который вы описали - частный случай - мне подходит / спасибо. Буду думать о компактном представлении реверснутого графа.
18 окт 21, 19:26    [22385211]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
Все форумы / Программирование Ответить