Ich habe diese Aufgabe Frage und ich habe absolut keine Ahnung, wie man die richtige Antwort bekommen, weiß jemand, was die richtige Antwort dafür wäre?Wie entwerfe ich einen Algorithmus, um die optimale Lösung für die Anzahl der Änderungen zu finden?
A) Eine n-Tages-Konferenz soll an einer Universität stattfinden.
Für jeden Tag dieser Konferenz ist genau ein großer Konferenzraum erforderlich, und es wird den ganzen Tag verwendet.
Es gibt m Tagungsräume an der Universität, die groß genug für diese Konferenz sind. Keines dieser Zimmer steht jedoch an jedem Tag der Konferenz zur Verfügung.
Zum Glück steht an jedem der n Tage mindestens ein Meetingraum zur Verfügung, so dass es immer noch möglich ist, die Konferenz an der Universität abzuhalten ( ).
Jedes Mal, wenn die Konferenz von einem Raum in den nächsten geschaltet wird, muss viel Arbeit getan werden, einschließlich des Verschiebens neuer Bücher auf dem Display, Bulletin Boards, Stellenausschreibungen, usw. Unser Ziel ist die Wahl der Raumzuweisungen bei gleichzeitiger Minimierung der Gesamtzahl der Raumänderungen.
Die Aufgabe besteht darin, einen Algorithmus zu entwickeln, um eine optimale Lösung für dieses Problem zu finden. Die Eingabe in den Algorithmus ist genauer gesagt eine m × n Matrix A, in der A [i, j] = 1 ist, wenn der Konferenzraum i für die Konferenz am j-ten Tag der Konferenz verfügbar ist, und & amp; # 981; A [i, j] = 0 sonst.
Es gibt mindestens eine 1 in jeder Spalte der Tabelle.
Tabelle 1 gibt ein Beispiel der Eingabetabelle, in denen m = 3 und n = 8.
m/n 1 2 3 4 5 6 7 8
1 0 0 0 1 0 1 1 1
2 1 1 1 0 0 1 1 1
3 1 1 0 1 1 1 0 0
Der Ausgang ist ein Array S [1..n], in welches S [d] = r wenn und nur wenn der Besprechungsraum r für die Konferenz am d-ten Tag benutzt wird. Für einen Index i des Arrays mit 1 ≤ i ≤ n-1 bedeutet die Ungleichung S [i] ̸ = S [i + 1] also, dass am (i + 1) -ten Tag eine Raumänderung auftritt. Ziel ist es, die Anzahl der Raumänderungen zu minimieren. Im obigen Beispiel ist eine optimale Lösung S = [2, 2, 2, 3, 3, 1, 1, 1], was zwei Raumänderungen erfordert. Beachten Sie, dass die optimale Lösung nicht eindeutig sein muss.
Eine mögliche gierige Strategie besteht darin, den Raum mit der größten Anzahl verfügbarer Tage auszuwählen und dann alle Tage zu verwenden, die für die Konferenz verfügbar sind.
Wählen Sie als Nächstes das Zimmer mit der zweitgrößten Anzahl verfügbarer Tage (mit Ausnahme der Tage, die bereits bearbeitet wurden) und verwenden Sie alle verfügbaren Tage, ohne die bereits behandelten Tage.
Wiederholen Sie diesen Vorgang. Nach dieser Strategie ist das Ausgangs-Array für das obige Beispiel S = [2,2,2,3,3,2,2,2] und zwei Raumänderungen werden durchgeführt. Zeigen Sie, dass diese Strategie nicht immer eine optimale Lösung bietet, indem Sie ein Gegenbeispiel konstruieren. Erkläre, warum die Lösung nicht optimal ist.
B) Entwerfen Sie einen effizienten Greedy-Algorithmus für das in Frage A beschriebene Problem, das immer eine optimale Lösung findet. Wenn Sie die Richtigkeit Ihres Algorithmus begründen, beweisen Sie sorgfältig, dass Ihre gierige Strategie immer eine optimale Lösung bietet.
Sie fragen viel hier, es ist leicht zu sagen, Sie haben keine Ahnung. Meiner Meinung nach sollte MINDESTENS ein Gegenbeispiel für den gegebenen Beispiel-Greedy-Algorithmus finden. Und versuchen Sie, sich etwas Mühe zu machen, was Sie bisher versucht haben und wo Sie stecken bleiben. –
Die [Hilfe/zum Thema] sagt eindeutig * Fragen, die nach Hausaufgabenhilfe fragen, müssen eine Zusammenfassung der bisherigen Arbeit enthalten um das Problem zu lösen, und eine Beschreibung der Schwierigkeit, die Sie haben, es zu lösen. *. * Ich habe die Aufgabe hier kopiert und eingefügt * ist nicht * Arbeit, die du bisher geleistet hast, um das Problem zu lösen *. Wenn Sie mit Ihrer Aufgabe nicht beginnen können, bitten Sie Ihren Lehrer um Hilfe. Sie werden bezahlt, um Ihnen das notwendige Wissen zu geben, um Ihre Aufgaben zu erfüllen, und entweder haben sie das noch nicht getan oder Sie waren im Unterricht unaufmerksam. In beiden Fällen liegt die Verantwortung bei Ihrem Lehrer. –