powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача оптимизации
13 сообщений из 38, страница 2 из 2
Задача оптимизации
    #40104772
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если все нужны, тогда и циклы нужны, и комбинации циклов. А так да, алгоритмов дофига, и зачем было здесь спрашивать?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104931
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.

Тогда простая рекурсия. Но она зациклится есть есть хоть одно кольцо.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104947
Фотография Верблюд
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.


"всех" путей может оказаться бесконечно много.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104976
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если хороводы кругами не не накручивать, бесконечностей не будет.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104989
Фотография Верблюд
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
Если хороводы кругами не не накручивать, бесконечностей не будет.


Тогда в задаче следует указать "не накручивая хороводы". Иначе непонятно будет чего хотят.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105088
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сделал примерно так:
Поиск в глубину запоминает альтернативные вершины для продолжения поиска в стеке.
При прохождении вершины в ней запоминается глубина стека.
На каждом шаге сначала проверяем это значение для новой вершины - В.
Если вершину не посещали - запоминаем глубину и продолжаем.
Иначе просматриваем все вершины и заменяем значение в них на мин(В, значение вершины) (**)
И специальные значения если через вершину (не) проходит путь ведущий к выходу.

Проблематично как мне видится действие (**).
Просмотр всех N вершин в худшем случае выполнится N раз. В итоге O(N^2)
Можно ли сделать быстрее?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105091
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В коде нагляднее.


Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
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 ....
	
}


...
Рейтинг: 0 / 0
Задача оптимизации
    #40105096
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

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

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

PS: множества <куда, откуда> и <откуда, куда> естественно MultiMap (т.е. позволяют хранить несколько ключей)
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105111
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

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

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


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

Ну и в заключениу к вашему "отжигному" алгоритму - достижимые конечные состояния нужно сначала найти. Это 5 цикл O(N)
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105116
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

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

В моей задаче нету входного сигнала следователно это не КА, следовательно методы для ДКА и НКА не применимы.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105136
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)
_дух_,
вот вы упёртый


вы можете вести диалог на уровне, без оскорблений и перехода на личности?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105157
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

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

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

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

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


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

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

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

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

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

Всё просто?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105271
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

А есть ещё поговорка - если у бабушки есть член то он уже дедушка.
Да, как вы написали сделать можно, но это как бы сказать -странно- привести задачу к общему случаю для того что бы реализовать решение для частного случая. И третий пункт задачи минимизации ДКА нам не нужен. Ну да бог с ним, а вот алгоритм который вы описали - частный случай - мне подходит / спасибо. Буду думать о компактном представлении реверснутого графа.
...
Рейтинг: 0 / 0
13 сообщений из 38, страница 2 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача оптимизации
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]