Профил
Loading...
+ Нов въпрос
djc_bg2015 avatar djc_bg2015 923 Точки

[Homework] Greedy Algorithms - Problem 1-5 Въпроси

Здравейте,

подхванах задачите от домашното и се оказва че имам нужда от млако помощ.

Относно задача 2: Подреждам процесите по стойност, но немога да измисля по какъв критерии да сравнявам следващия процес, така че да съм сигурен че ще може да се изпълни ако го добавя в изхода.

Всякаква подсказка ще ми е добре дошла :)

Относно задача 3: Използвам правилото на Warnsdorf, но резултата се разминава  спрямо показаните примери (само на дъската 5 х 5 получавам 1:1 резултат. Изпълнявам всеки ход, взимайки полето с най - млако следващи възможни продължения.). Нормално л ие да има частично разминаване, или това значи че алгоритъма не работи както се очаква?

Благодаря предварително!

 

Тагове:
0
Структури от данни и алгоритми 04/11/2015 14:00:57
Filkolev avatar Filkolev 4482 Точки

На задачата с коня важното е да се запълни дъската. Разминаване може да има ако имаш повече от една клетка с еднаква стойност; при равенство ти може би взимаш по друг критерий клетката. Ако дъската е пълна с правилните числа всичко е наред :)

На 2-ра - това мисля е единствената затрудняваща част от домашното. Не съм я решавал, но ми се върти в главата идея за масив, по някакъв начин да се пазят възможните комбинации. Например, взимаме процеса с най-голяма стойност и го слагаме по индекс на възможно най-крайната позиция; ако не можем (има вече там сложен процес) гледаме предходните позиции и така докато не запълним масива. Не гарантирам, че ще работи, нито че е оптимално. Но е идея, може да пробваш и после да кажеш дали логиката е вярна.

 

0
03/11/2015 20:47:23
djc_bg2015 avatar djc_bg2015 923 Точки

Мерси за отговора :)

Ще се пробвам утре на свежа глава и ще пиша, когато имам резултат.

Поздрави!

0
djc_bg2015 avatar djc_bg2015 923 Точки

Ами направих го по следния начин:

взимам листа с вече добавените таскове и следващия таск, който трябва да се добави.

Слагам всичко в нов лист от таскове (temp), подреждам ги по deadline, и въртя форийч като инкрементирам една променлива step=1. За всяка стъпка проверявам дали елемента който е наред има deadline < step. Ако няма такъв елемент значи новия таск може да бъде добавен, ако пък има такъв елемент брейквам форийча и продължавам към следващия таск.

 

Доста завъртяно стана, но пък изглежда да работи...

0
Ivaka127 avatar Ivaka127 20 Точки

На задача 3та за Knight Tour, има значение в какъв ред проверяваш стойността на потенциалната клетка. Направил съм малко reverse engineering и трите отговора ми се получават 1:1 със следната последователност на ходове от коня:
 

public static int[,] knightMoves = new int[,]
{
    { +1, +2 },
    { -1, +2 },
    { +2, +1 },
    { +1, -2 },
    { -1, -2 },
    { -2, +1 },
    { +2, -1 },
    { -2, -1 }
};


Друго - при изчисляване на броя потенциални ходеве, се взима предвид вече клетките, където конят е минал и те не се смятат.

 

На задача 2ра за Processor Scheduling, на всяка стъпка изчислявам приоритет на всички останали таскове, като изпълнявам таска с най-голям приоритет:
 

double taskPriority = taskValue / (taskDeadline - stepCount);

 

3
04/11/2015 11:53:15
djc_bg2015 avatar djc_bg2015 923 Точки

Ами да, рзбрах, че там е проблема в последствие :)

Ето как проверявам аз в момента (отговорите се разминават):

var possibleMoves = new[]
{
    new {Row = -2, Col = 1},
    new {Row = -1, Col = 2},
    new {Row = 1, Col = 2},
    new {Row = 2, Col = 1},
    new {Row = 2, Col = -1},
    new {Row = 1, Col = -2},
    new {Row = -1, Col = -2},
    new {Row = -2, Col = -1},
};

 

Относно задача 2 - много добре си се сетил :)

0
04/11/2015 12:29:15
krach avatar krach 65 Точки

За задача 3 не мисля че е от ъществено значение дали 5тия ход примерно ще ти е в една или друга клетка, след като резултата е верен. Нямаш в условието на позиция X и Y да е определена стойност, така че....

Моя вариант на 3
https://github.com/krachunov/Algorithms/blob/master/src/homeWork7/KnightTour.java

1
Ivaka127 avatar Ivaka127 20 Точки

Да, колега, прав си, задача 3 има повече от едно вярно решение. Просто ми беше интересно при какви условия ще получа абсолютно същия резултат, малко безмислено от моя страна.

0
04/11/2015 12:59:52
dim4o avatar dim4o 288 Точки

Аз не съм сигурен, че разбирам правилно условието на 2-ра задача. Може ли някой да даде още примери с input/output? Какво пречи да вземем най-големия deadline и толкова на брой пъти да вземем най-високите tasks по стойност и после да сортираме резултата. Защо това няма да работи?

EDIT: Сега се замислих и май схванах какво се иска. Изглежда лесно. Въпреки това ще е полезно да се видят още примери.

0
04/11/2015 17:49:02
moholovka avatar moholovka 169 Точки

https://github.com/IvanMladenov/Algorithms/tree/master/GreedyAlgorithms/ProcessorScheduling

Моето решение на втора, на третия пример последователността е различна но тотала е същия и според мен ще работи вярно при различни входове. В репозиторито има и на първа решение.

 

EDIT: Допълвам и с коня, не ми съвпада с нито един от примерите, но работи вярно, поне за първите два примера го проверих.

https://github.com/IvanMladenov/Algorithms/blob/master/GreedyAlgorithms/KnightsTour/Program.cs

1
05/11/2015 01:31:19
Innos avatar Innos 419 Точки

Поздравления колега, твоето решение на 2ра задача е най-доброто което видях. Много хитър начин на обхождане, който не само че спазва greedy изискванията, но и ще произвежда най-оптималното решение всеки път, без излишни проверки.

Edit: Само бих сложил 1 проверка точно преди да extract-неш от BinaryHeap-a дали BinaryHeap-a е празен, за да можеш да предотвратиш ситуации от рода на имаш 1 таск с Deadline 5 и 0 с deadline 4, на deadline 5 вкарваш таска и го вадиш в резултатите, но на 4 ако няма нищо и BinaryHeap-а е празен ще гръмне като се опиташ да вадиш.

0
08/11/2015 16:46:50
aanguelov avatar aanguelov 219 Точки

Здравейте, домашното от Greedy Algorithms не е пуснато за оценяване.

0
Filkolev avatar Filkolev 4482 Точки

Да, малко досаден проблем. Сложен е краен срок за оценяване, но като не е избран тип оценяване пак няма как да се оценява. Оправено е вече.

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.