Verwenden von C++ am Beispiel des Reise-Optimierers von Bing Maps

In diesem Dokument wird die C++-Komponente des Reise-Optimierers von Bing Maps beschrieben. Die C++-Komponente verwendet reinen systemeigenen Code, um die Logik der Routenoptimierung und den Code für Komponentenerweiterungen für Visual C++ (C++/CX) für die Kommunikation mit anderen Windows-Runtime-Komponenten zu implementieren.

Hinweis

Weitere Informationen zu C++/CX, den Spracherweiterungen, die für eine in C++ geschriebene Windows Store-App verfügbar sind, finden Sie unter Sprachreferenz zu Visual C++ (C++/CX).

Informationen zum Erstellen einer grundlegenden Windows-Runtime-Komponente in C++ finden Sie unter Exemplarische Vorgehensweise: Erstellen einer grundlegenden Windows-Runtime-Komponente in C++ und Aufrufen dieser Komponente über JavaScript oder C#.

Der C++-Teil der App wird als Windows-Runtime Dynamic Link Library (DLL) geschrieben. Diese Bibliothek bietet folgende Funktionen:

• Breiten- und Längengrad der einzelnen Standorte vom Bing Maps-Webdienst abrufen. Dieser Vorgang verwendet die Bing Maps-REST-Schnittstelle (Representational State Transfer).

• Die Entfernung zwischen jedem möglichen Standortpaar der Reiseroute abrufen. Dieser Vorgang verwendet ebenfalls die Bing Maps-REST-Schnittstelle.

• Die Routenoptimierung ausführen. Dieser Vorgang verwendet den Ameisenalgorithmus und die Parallelverarbeitung, um die optimierte Route effizient zu berechnen.

Diese Vorgänge werden asynchron oder im Hintergrund ausgeführt. So bleibt die Benutzeroberfläche während des Optimierungsprozesses reaktionsfähig.

Im Folgenden sind einige der wichtigen Funktionen und Technologien aufgeführt, die die C++-Komponente verwendet:

• concurrency::create_async zum Erstellen eines Windows::Foundation::IAsyncOperationWithProgress<TResult, TProgress>-Objekts. Die JavaScript-App verwendet dieses Objekt zur Überwachung des Status und des Abschlusses sowie zum Abbrechen der Optimierungsaufgabe. Die Komponente verwendet concurrency::task zur Kommunikation mit Bing Maps und zur Ausführung der Optimierungsaufgabe im Hintergrund.

• Bing Maps-REST-Dienste zum Abrufen von Orts- und Routeninformationen.

• IXMLHTTPRequest2 zum asynchronen Anfordern und Lesen von HTTP-Streams vom Bing Maps-REST-Dienst.

• Windows::Data::Xml::Dom::XmlDocument zum Lesen von Antworten vom Bing Maps-Webdienst.

• Der concurrency::parallel_for_each-Algorithmus dient zum Parallelisieren des Routenoptimierungsalgorithmus.

Hinweis

Den diesem Dokument entsprechenden Beispielcode finden Sie unter Beispiel für Bing Maps-Reise-Optimierer.

Inhalt dieses Dokuments

• Codekonventionen

• Dateiorganisation

• Erstellen der Klassen TripOptimizer und TripOptimizerImpl

• Komponentenworkflow

  • Phase 1: Abrufen von Standortdaten

  • Phase 2: Abrufen von Routendaten

  • Phase 3: Berechnen der optimierten Route

• Definieren von HTTP-Funktionalität

• Berechnen der optimalen Route

• Behandlung von Abbrüchen

• Migration von ActiveX

• Nächste Schritte

Codekonventionen

Neben Windows-Runtime verwendet die C++-Komponente zum Erstellen der Windows Store-Komponente moderne Codekonventionen wie intelligente Zeiger und die Ausnahmebehandlung.

Windows-Runtime ist eine Programmierschnittstelle, die Sie verwenden können, um Windows Store-Apps zu erstellen, die nur in einer vertrauenswürdigen Betriebssystemumgebung ausgeführt werden. Solche Apps verwenden autorisierte Funktionen, Datentypen und Geräte und werden über den Windows Store vertrieben. Windows-Runtime wird durch die ABI (Application Binary Interface) dargestellt. Die ABI ist ein zugrunde liegender binärer Vertrag, der Windows-Runtime-APIs für Programmiersprachen wie Visual C++ verfügbar macht.

Um das Schreiben von Apps zu erleichtern, die Windows-Runtime verwenden, stellt Microsoft Spracherweiterungen für Visual C++ bereit, die speziell Windows-Runtime unterstützen. Viele dieser Spracherweiterungen ähneln der Syntax für die Sprache C++-/CLI. Systemeigene Apps verwenden diese Syntax jedoch nicht für die CLR (Common Language Runtime), sondern für die Windows-Runtime. Der Dach-Modifizierer (^) stellt einen wichtigen Bestandteil dieser neuen Syntax dar, da er das automatische Löschen von Laufzeitobjekten mithilfe der Verweiszählung ermöglicht. Statt Methoden wie AddRef und Release aufzurufen, um die Lebensdauer eines Windows-Runtime-Objekts zu verwalten, löscht die Laufzeit das Objekt, sofern keine andere Komponente darauf verweist, wenn es sich beispielsweise nicht im Gültigkeitsbereich befindet oder wenn Sie alle Verweise auf nullptr festlegen. Ein anderer wichtiger Bestandteil von Visual C++ zum Erstellen von Windows Store-Apps ist das Schlüsselwort ref new. Verwenden Sie ref new anstelle von new, um nach Verweis gezählte Windows-Runtime-Objekte zu erstellen. Weitere Informationen finden Sie unter Windows-Runtime-Objekte und "ref new".

Wichtig

Sie müssen ^ und ref new nur dann verwenden, wenn Sie Windows-Runtime-Objekte oder Windows-Runtime-Komponenten erstellen.Sie können die C++-Standardsyntax verwenden, wenn Sie Kernanwendungscode schreiben, der Windows-Runtime nicht verwendet.

Hinweis

Der Reise-Optimierer von Bing Maps verwendet ^ zusammen mit Microsoft::WRL::ComPtr, std::shared_ptr und std::unique_ptr, um vom Heap zugewiesene Objekte zu verwalten und Speicherverluste zu minimieren.Es wird empfohlen, den Modifizierer ^ zum Verwalten der Lebensdauer von Windows-Runtime-Variablen, Microsoft::WRL::ComPtr zum Verwalten der Lebensdauer von COM-Variablen und shared_ptr oder unique_ptr zum Verwalten der Lebensdauer aller anderen C++-Objekte zu verwenden, die vom Heap zugewiesen werden.

Weitere Informationen zur modernen C++-Programmierung finden Sie unter Willkommen zurück bei C++ (Modern C++). Weitere Informationen zu den Spracherweiterungen, die für Windows Store-Apps für C++ zur Verfügung stehen, finden Sie unter Sprachreferenz zu Visual C++ (C++/CX).

[Nach oben]

Dateiorganisation

In der folgenden Liste wird kurz die Rolle jeder Quellcodedatei beschrieben, die Bestandteil der C++-Komponente ist.

• AntSystem.h, AntSystem.cpp
  Definiert den Ameisenalgorithmus und die unterstützenden Datenstrukturen.

• HttpRequest.h, HttpRequest.cpp
  Definiert die HttpRequest-Klasse, die eine Hilfsklasse zum Ausführen von asynchronen HTTP-Anforderungen ist.

• pch.h, pch.cpp
  Der vorkompilierte Header für das Projekt.

• TripOptimizer.h, TripOptimizer.cpp
  Definiert die TripOptimizer-Klasse, die als Schnittstelle zwischen der App und der Kernkomponentenlogik dient.

• TripOptimizerImpl.h, TripOptimizerImpl.cpp
  Definiert die TripOptimizerImpl-Klasse, die die Kernlogik der Komponente definiert.

[Nach oben]

Erstellen der Klassen TripOptimizer und TripOptimizerImpl

Die C++-Komponente enthält eine Windows-Runtime-Klasse, TripOptimizerComponent::TripOptimizer, die mit anderen Windows-Runtime-Komponenten kommunizieren kann. Im Reise-Optimierer von Bing Maps kommuniziert diese Klasse mit dem JavaScript-Teil der App. (Da die C++-Komponente als DLL geschrieben wird, können Sie sie auch mit anderen Apps verwenden.) Die TripOptimizer-Klasse definiert nur die Methoden, die mit anderen Windows-Runtime-Komponenten kommunizieren. Die Implementierungsdetails werden von der TripOptimizerImpl-Klasse bearbeitet. Wir haben dieses Muster ausgewählt, um die öffentliche Schnittstelle besser zu kapseln und von den Implementierungsdetails zu trennen. Weitere Informationen zu diesem Muster finden Sie unter pimpl für Compilierungszeitkapselung (Modern C++).

// Defines the TripOptimizer class. This class interfaces between the app
// and the implementation details.
public ref class TripOptimizer sealed 
{
public:
    TripOptimizer();

    // Optimizes a trip as an asynchronous process.
    Windows::Foundation::IAsyncOperationWithProgress<
        Windows::Foundation::Collections::IMap<
            Platform::String^, 
            Windows::Foundation::Collections::IVector<Platform::String^>^>^, 
        Platform::String^>^ OptimizeTripAsync(
            Windows::Foundation::Collections::IVector<Platform::String^>^ waypoints, 
            Platform::String^ travelMode, 
            Platform::String^ optimize,
            Platform::String^ bingMapsKey, 
            double alpha, double beta, double rho,
            unsigned int iterations, bool parallel);

private:
    ~TripOptimizer();
    // Defines implementation details of the optimization routine.
    std::unique_ptr<Details::TripOptimizerImpl> m_impl;
};

Wichtig

Wenn Sie eine Komponentenklasse für Windows-Runtime erstellen, die für andere externe Komponenten freigegeben werden kann, müssen Sie die Schlüssselwörter public und sealed verwenden.Weitere Informationen zum Erstellen einer Windows-Runtime-Komponente in C++, die von einer Windows Store-App aufgerufen werden kann, finden Sie unter Erstellen von Windows-Runtime-Komponenten in C++.

Mit der TripOptimizer::OptimizeTripAsync-Methode kommuniziert eine App mit der C++-Komponente. Diese Methode startet die Abfolge der Aufgaben, mit denen die optimierte Reiseroute berechnet wird. Der Aufrufer verwendet den Rückgabewert, um den Status und den Abschluss der Optimierungsaufgabe zu überwachen. Er wird auch verwendet, um den Vorgang abzubrechen. Das Abbrechen wird im Abschnitt Behandlung von Abbrüchen weiter unten in diesem Dokument erläutert.

Die Methode TripOptimizer::OptimizeTripAsync verzögert das Ausführen der Aktion durch die TripOptimizerImpl-Klasse. TripOptimizerImpl wird weiter unten in diesem Dokument ausführlicher beschrieben.

// Optimizes a trip as an asynchronous process.
IAsyncOperationWithProgress<IMap<String^, IVector<String^>^>^, String^>^ 
TripOptimizer::OptimizeTripAsync(
    IVector<String^>^ waypoints, 
    String^ travelMode, 
    String^ optimize,
    String^ bingMapsKey, 
    double alpha, double beta, double rho,
    unsigned int iterations, bool parallel)
{
    // Forward to implementation.    
    return m_impl->OptimizeTripAsync(waypoints,travelMode, optimize, bingMapsKey,
        alpha, beta, rho, iterations, parallel);
}

[Nach oben]

Komponentenworkflow

Die TripOptimizer::OptimizeTripAsync-Methode startet die Abfolge der Vorgänge, mit denen die optimierte Reiseroute berechnet wird. Diese Methode verhält sich asynchron, damit die Anwendung reaktionsfähig bleibt. Um asynchrones Verhalten zu ermöglichen, gibt diese Methode Windows::Foundation::IAsyncOperationWithProgress <TResult, TProgress> zurück. Eine Windows-Runtime-Komponente, die diese Methode aufruft, kann mithilfe dieses Objekts den Rückgabewert abrufen, wenn dieser verfügbar ist. Diese Schnittstelle ermöglicht zudem dem Aufrufer, den Status des Vorgangs zu überwachen und auftretende Fehler zu empfangen.

Tipp

Folgende Vorgehensweise wird empfohlen: Der Name einer asynchronen Methode sollte mit Async enden, und die Methode sollte Windows::Foundation::IAsyncAction, Windows::Foundation::IAsyncActionWithProgress<TProgress>, Windows::Foundation::IAsyncOperation<TResult> oder Windows::Foundation::IAsyncOperationWithProgress<TResult, TProgress> zurückgeben.

Jede für Windows-Runtime aktivierte Sprache (C++, JavaScript usw.) schreibt eine eigene Methode zum Erstellen eines asynchronen Vorgangs vor. In C++ können Sie die concurrency::create_async-Funktion verwenden. Diese Funktion gibt ein IAsyncAction-, IAsyncActionWithProgress<TProgress>-, IAsyncOperation<TResult>- oder ein IAsyncOperationWithProgress<TResult, TProgress>-Objekt zurück. Der Rückgabetyp hängt von der Signatur des Funktionsobjekts ab, das Sie übergeben. Da beispielsweise die TripOptimizerImpl::InternalOptimizeTripAsync-Methode ein concurrency::progress_reporter-Objekt als Parameter akzeptiert und einen Nicht-void-Wert zurückgibt, gibt create_async IAsyncOperationWithProgress<TResult, TProgress> zurück. Wenn diese Methode void zurückgeben soll, müsste create_async IAsyncActionWithProgress<TProgress> zurückgeben. Weitere Informationen über create_async und über die Zusammenarbeit mit Windows 8 finden Sie unter Erstellen von asynchronen Vorgängen in C++ für Windows Store-Apps.

Der folgende Code veranschaulicht die TripOptimizerImpl::OptimizeTripAsync-Methode.

// Optimizes a trip as an asynchronous process.
IAsyncOperationWithProgress<IMap<String^, IVector<String^>^>^, String^>^ 
    TripOptimizerImpl::OptimizeTripAsync(
    IVector<String^>^ waypoints, 
    String^ travelMode,
    String^ optimize,
    String^ bingMapsKey,
    double alpha, double beta, double rho,
    unsigned int iterations, bool parallel)
{
    // Copy inputs to a OptimizeTripParams structure.
    auto params = make_shared<OptimizeTripParams>();
    for (auto waypoint : waypoints)
    {
        params->Waypoints.push_back(waypoint->Data());
    }
    params->TravelMode = wstring(travelMode->Data());
    params->Optimize = wstring(optimize->Data());
    params->BingMapsKey = UriEncode(bingMapsKey->Data());
    params->Alpha = alpha;
    params->Beta = beta;
    params->Rho = rho;
    params->Iterations = iterations;
    params->Parallel = parallel;

    // Perform the operation asynchronously.
    return create_async([this, params](progress_reporter<String^> reporter, 
        cancellation_token cancellationToken) -> task<IMap<String^, IVector<String^>^>^>
    {
        // Create a linked source for cancellation.
        // This enables both the caller (through the returned 
        // IAsyncOperationWithProgress object) and this class to set
        // the same cancellation token.
        m_cancellationTokenSource = 
            cancellation_token_source::create_linked_source(cancellationToken);

        // Perform the trip optimization.
        return InternalOptimizeTripAsync(params, cancellationToken, reporter)
            .then([this](task<IMap<String^, IVector<String^>^>^> previousTask) -> IMap<String^, IVector<String^>^>^
        {
            try
            {
                return previousTask.get();
            }
            catch (const task_canceled&)
            {
                return nullptr;
            }
        });
    });
}

Das progress_reporter-Objekt sendet Statusmeldungen an den Aufrufer. Das cancellation_token-Objekt aktiviert die Komponente, um auf Abbruchanforderungen zu reagieren. (Das Abbrechen wird im Abschnitt Behandlung von Abbrüchen in diesem Dokument beschrieben.) Weitere Informationen dazu, wie der JavaScript-Teil der App mit diesem asynchronen Vorgang funktioniert, der von TripOptimizer::OptimizeTripAsync zurückgegeben wird, finden Sie unter Interoperation zwischen JavaScript und C++ am Beispiel des Reise-Optimierers von Bing Maps.

Die Arbeitsfunktion, die für create_async in TripOptimizer::OptimizeTripAsync bereitgestellt wird, gibt ein task-Objekt zurück. Sie können einen Wert, T, oder eine Aufgabe, task<T>, von create_async zurückgeben. Wir geben task<T> zurück, damit wir nicht auf das Ergebnis der Hintergrundaufgaben warten müssen. Stattdessen wird das Ergebnis von der Laufzeit abgerufen, sobald es verfügbar ist, und an den Aufrufer weitergegeben. Es wird empfohlen, dieses Muster nach Möglichkeit beizubehalten.

Die TripOptimizer.cpp-Datei definiert die task_from_result-Hilfsfunktion, die ein task-Objekt zurückgibt, das sofort mit dem angegebenen Ergebnis abgeschlossen wird. Diese Funktion ist nützlich, wenn Sie eine Funktion schreiben, die task zurückgibt, und diese Funktion mit einem bestimmten Ergebnis früh zurückgegeben wird.

// Creates a task that completes with the provided result.
template <typename Result>
task<Result> task_from_result(Result result)
{
    return create_task([result]() -> Result { return result; });
}

Die folgende Abbildung veranschaulicht den Ablauf von Vorgängen, die auftreten, wenn eine externe Komponente TripOptimizer::OptimizeTripAsync aufruft, um den Optimierungsprozess zu starten.

Die TripOptimizerImpl::OptimizeTripAsync-Methode ruft die TripOptimizerImpl::InternalOptimizeTripAsync-Methode im Rahmen des asynchronen Vorgangs auf. Die TripOptimizerImpl::InternalOptimizeTripAsync-Methode ruft TripOptimizerImpl::CreateGraph auf, um ein Diagramm zu erstellen, das die Reise darstellt. Jeder Standort wird durch einen Knoten dargestellt, und jedes Knotenpaar wird durch einen Rand verbunden. Ein Knoten enthält Informationen über einen Standort, wie den Namen, den Breiten- und den Längengrad. Ein Rand enthält die Entfernung zwischen einem Knotenpaar.

// Creates the graph of objects that represents the trip topography.
void TripOptimizerImpl::CreateGraph(
    const vector<wstring>& waypoints, 
    vector<shared_ptr<Node>>& nodes,
    vector<shared_ptr<Edge>>& edges)
{
    //
    // Create a Node object for each waypoint in the array.
    // Each element of the waypoints array contains a string that represents 
    // a location (for example, "Space Needle, WA").
    //

    for (const wstring& waypoint : waypoints)
    {
        // Add a Node object to the collection.
        nodes.push_back(make_shared<Node>(waypoint));
    }

    //
    // Create edges that form a fully-connected graph.
    //

    // Connect every node to every other node.
    for (auto iter = begin(nodes); iter != end(nodes); ++iter)
    {
        auto node1 = *iter;
        for_each(iter + 1, end(nodes), [this, &node1, &edges](shared_ptr<Node> node2)
        {
            // Create edge pair.
            edges.push_back(make_shared<Edge>(node1, node2));
        });
    }
}

Die TripOptimizerImpl::InternalOptimizeTripAsync-Methode führt die Reiseoptimierung in drei Phasen aus. In der ersten Phase ruft diese Methode Standortdaten von Bing Maps ab. In der zweiten Phase ruft sie Routeninformationen zwischen jedem möglichen Standortpaar der Reiseroute ab. In der dritten Phase wird der Reiseoptimierungsalgorithmus ausgeführt. Jede Phase wird als Aufgabenfortsetzung der vorherigen Phase verstanden. Fortsetzungen ermöglichen es, eine oder mehrere Aufgaben auszuführen, nachdem eine andere Aufgabe abgeschlossen ist. Fortsetzungen werden ausführlich weiter unten in diesem Dokument beschrieben. Beachten Sie jedoch, dass Sie aufgrund der Tatsache, dass eine Fortsetzung im Hintergrund ausgeführt wird, Variablen speichern müssen, die für die Aufgaben freigegeben werden, damit diese später darauf zugreifen können. Die TripOptimizerImpl-Klasse definiert die OptimizeTripParams-Struktur. Diese Struktur enthält die Eingaben für die TripOptimizerImpl::InternalOptimizeTripAsync-Methode und die Variablen, die für die Aufgaben, die den Gesamtvorgang bilden, freigegeben werden.

// Holds variables that are used throughout the trip optimization process.
// We create this stucture so that common parameters can be easily passed among
// task continuations. 
struct OptimizeTripParams
{
    // 
    // The inputs to OptimizeTripAsync

    std::vector<std::wstring> Waypoints;
    std::wstring TravelMode;
    std::wstring Optimize;
    std::wstring BingMapsKey;
    double Alpha;
    double Beta;
    double Rho;
    unsigned long Iterations;
    bool Parallel;

    //
    // Timer variables

    // The following times are sent as part of a progress message.
    // The overall time.
    ULONGLONG TotalTime;
    // The overall time and the spent performing HTTP requests.
    ULONGLONG HttpTime;   
    // The time spent performing the optimization algorithm.
    ULONGLONG SimulationTime;

    //
    // Location graph.

    // A collection of Node objects. There is one Node object for each location.
    std::vector<std::shared_ptr<AntSystem::Node>> Nodes;

    // A collection of Edge objects. There are
    // (n * (n - 1) / 2) edges, where n is the number of nodes.
    std::vector<std::shared_ptr<AntSystem::Edge>> Edges;

    // The number of pending HTTP requests for the current batch.
    long RequestsPending;

    // Holds the unresolved locations for the first phase of the optimization process.
    concurrency::concurrent_vector<std::shared_ptr<AntSystem::Node>> UnresolvedLocations;
};

Die TripOptimizerImpl::OptimizeTripAsync-Methode erstellt eine OptimizeTripParams-Struktur (mithilfe eines std::shared_ptr-Objekts) und übergibt sie an jede Fortsetzung in der Aufgabenkette.

// Copy inputs to a OptimizeTripParams structure.
auto params = make_shared<OptimizeTripParams>();
for (auto waypoint : waypoints)
{
    params->Waypoints.push_back(waypoint->Data());
}
params->TravelMode = wstring(travelMode->Data());
params->Optimize = wstring(optimize->Data());
params->BingMapsKey = UriEncode(bingMapsKey->Data());
params->Alpha = alpha;
params->Beta = beta;
params->Rho = rho;
params->Iterations = iterations;
params->Parallel = parallel;

Hinweis

Diese Variablen hätten wir auch als direkte Member der TripOptimizerImpl-Klasse erstellen können.Durch Bereitstellen einer Parameterstruktur wird der Zustand eines Reiseoptimierungsvorgangs jedoch der entsprechenden Aktion besser zugeordnet.Wenn wir Membervariablen verwendet hätten, wäre es schwieriger, Funktionen wie das gleichzeitige Ausführen mehrerer Reiseoptimierungen zu unterstützen.

Phase 1: Abrufen von Standortdaten

In der ersten Phase ruft die TripOptimizerImpl::InternalOptimizeTripAsync-Methode Standortdaten von Bing Maps ab. Standortdaten werden abgerufen, sodass der Benutzer bestätigen kann, dass Bing Maps über die richtige Eingabe verfügt. Wenn Sie beispielsweise "Frankfurt" angeben, weiß Bing Maps nicht, ob Sie "Frankfurt (Oder)", "Frankfurt am Main" oder "Frankfurt, BY" meinen. Die C++-Komponente muss die Entfernung zwischen jedem Standortpaar später abrufen. Wenn ein Standort mehrdeutig ist, müssen alle möglichen Standorte auf der Benutzeroberfläche angezeigt werden, damit der Benutzer einen Standort auswählen oder einen neuen eingeben kann. Die OptimizeTripParams::UnresolvedLocations-Variable verfolgt nicht aufgelöste Standorte. Wenn die TripOptimizerImpl::RetrieveLocationsAsync-Methode diesen Vektor mit Werten ausfüllt, werden sie von TripOptimizerImpl::InternalOptimizeTripAsync zurückgegeben.

//
// Phase 1: Retrieve the location of each waypoint.
//

//
params->HttpTime = GetTickCount64();

// Report progress.
reporter.report("Retrieving locations (0% complete)...");

auto tasks = RetrieveLocationsAsync(params, cancellationToken, reporter);

// Move to the next phase after all current tasks complete.
return when_all(begin(tasks), end(tasks)).then(
    [=](task<void> t) -> task<IMap<String^, IVector<String^>^>^> 
{
    // The PPL requires that all exceptions be caught and handled.
    // If any task in the collection errors, ensure that all errors in the entire
    // collection are observed at least one time.
    try
    {
        // Calling task.get will cause any exception that occurred 
        // during the task to be thrown.
        t.get();
    }
    catch (Exception^)
    {
        observe_all_exceptions<void>(begin(tasks), end(tasks));
        // Rethrow the original exception.
        throw;
    }
    catch (const task_canceled&)
    {
        observe_all_exceptions<void>(begin(tasks), end(tasks));
        // Rethrow the original exception.
        throw;
    }

    // Report progress.
    reporter.report("Retrieving locations (100% complete)...");

    // If there are unresolved locations, return them.
    if (params->UnresolvedLocations.size() > 0)
    {
        // Parallel arrays of input names to their possible resolved names.
        Vector<String^>^ inputNames;
        Vector<String^>^ options;

        auto locations = ref new Map<String^, IVector<String^>^>();

        // For each unresolved location, add the user input name and
        // the available options to the arrays.
        for (size_t i = 0; i < params->UnresolvedLocations.size(); ++i)
        {
            auto node = params->UnresolvedLocations[i];

            // Add options.
            options = ref new Vector<String^>();
            for (size_t j = 0; j < node->Names.size(); ++j)
            {
                options->Append(ref new String(node->Names[j].c_str()));
            }
            locations->Insert(ref new String(node->InputName.c_str()), options);
        }

        return task_from_result<IMap<String^, IVector<String^>^>^>(locations);
    }

Die TripOptimizerImpl::RetrieveLocationsAsync-Methode verwendet die concurrency::task-Klasse, um HTTP-Anforderungen als Hintergrundaufgaben zu verarbeiten. Da die HttpRequest-Klasse asynchron agiert, enthält TripOptimizerImpl::RetrieveLocationsAsync alle Hintergrundaufgaben und verwendet die concurrency::when_all-Funktion, um die Aufgaben zu definieren, die nach dem Abschluss der Hintergrundaufgaben als Nächstes ausgeführt werden. Da die TripOptimizerImpl::RetrieveLocationsAsync-Methode Teil der gesamten Hintergrundaufgabe ist, wird die Hauptanwendung nicht durch diese Kette von asynchronen Vorgangsaufgaben blockiert.

Details über die Funktion der HttpRequest-Klasse werden in diesem Dokument im Abschnitt Definieren von HTTP-Funktionalität erläutert.

// Retrieves information about the locations from the Bing Maps location service.
vector<task<void>> TripOptimizerImpl::RetrieveLocationsAsync(
    shared_ptr<OptimizeTripParams> params,
    cancellation_token cancellationToken,
    progress_reporter<String^> reporter)
{
    // Holds the tasks that process the returned XML documents.
    vector<task<void>> tasks;

    // Create HTTP requests for location information.
    auto nodes = params->Nodes;
    params->RequestsPending = static_cast<long>(params->Nodes.size()); // Used to report progress.
    for (auto node : nodes)
    {
        wstringstream uri;
        uri << L"http://dev.virtualearth.net/REST/v1/Locations?q=" 
            << UriEncode(node->InputName)
            << L"&o=xml&key=" << params->BingMapsKey;

        // Create a parent task that downloads the XML document.
        auto httpRequest = make_shared<HttpRequest>();
        auto downloadTask = httpRequest->GetAsync(
            ref new Uri(ref new String(uri.str().c_str())), 
            cancellationToken);

        // Create a continuation task that fills location information after 
        // the download finishes.
        tasks.push_back(downloadTask.then([=](task<wstring> previousTask)
        {
            (void)httpRequest;

            // Get the result to force exceptions to be thrown.
            wstring response = previousTask.get();

            try
            {
                // Create and load the XML document from the response.
                XmlDocument^ xmlDocument = ref new XmlDocument();
                auto xml = ref new String(response.c_str() + 1); // Bypass BOM.
                xmlDocument->LoadXml(xml);

                // Fill in location information.
                ProcessLocation(node, xmlDocument, params->UnresolvedLocations);
            }
            catch (Exception^)
            {
                // An error occurred. Cancel any active operations.
                m_cancellationTokenSource.cancel();
                // Rethrow the exception.
                throw;
            }

            // Report progress.
            wstringstream progress;
            progress << L"Retrieving locations (" 
                << static_cast<long>(100.0 * (params->Nodes.size() - params->RequestsPending) / params->Nodes.size())
                << L"% complete)...";
            reporter.report(ref new String(progress.str().c_str()));
            InterlockedDecrement(&params->RequestsPending);
        }));
    }

    return tasks;
}

Die TripOptimizerImpl::RetrieveLocationsAsync-Methode verwendet die concurrency::task::then-Methode auch, um jede ankommende Antwort von Bing Maps zu verarbeiten. Die task::then-Methode erstellt eine Fortsetzungsaufgabe. Hierbei handelt es sich um eine Aufgabe, die ausgeführt wird, nachdem die vorhergehende Aufgabe beendet ist. Mit dem Aufruf von when_all am Ende der TripOptimizerImpl::RetrieveLocationsAsync-Methode wird gewartet, bis alle Aufgaben und ihre Fortsetzungsaufgaben beendet sind. Weitere Informationen zu Aufgaben und Fortsetzungsaufgaben in C++ finden Sie unter Aufgabenparallelismus.

Die Bing Maps-REST-API gibt XML-Daten zurück. Die TripOptimizerImpl::ProcessLocation-Methode lädt Standortinformationen für einen Standort aus dem bereitgestellten XML-Datenstream. Diese Methode verwendet XmlDocument::SelectSingleNodeNS, um das angegebene XmlDocument-Objekt zu verarbeiten. Dieses Beispiel zeigt, wie die TripOptimizerImpl::ProcessLocation-Methode den Antwortcode für die Anforderung abruft:

// Move to response code.
// Report an error and return if the status code is 
// not 200 (OK).
xmlNode = xmlDocument->SelectSingleNodeNS(L"/d:Response/d:StatusCode/text()", ns);
if (xmlNode == nullptr) throw ref new NullReferenceException("Failed to parse status code from HTTP response");

Wichtig

Stellen Sie sicher, dass Sie die Notation text() verwenden, wenn Sie Textknoten mithilfe von XmlDocument::SelectSingleNodeNS aus einem XML-Dokument auswählen.

Die TripOptimizerImpl::ProcessLocation-Methode löst eine Ausnahme aus, wenn ein Fehler auftritt. In diesem Beispiel löst TripOptimizerImpl::ProcessLocation Platform::NullReferenceException aus, wenn das XML-Dokument nicht die erwarteten Daten enthält. Da dieser Fehler nicht behebbar ist, fängt die Komponente diese Ausnahme nicht ab. Wenn eine Ausnahme auftritt, wird diese daher an den Fehlerhandler der Hauptanwendung übergeben.

Die TripOptimizerImpl::ProcessLocation-Methode liest die Gesamtanzahl von Ressourcen aus dem XML-Stream. Eine Ressource verweist auf eine mögliche Entsprechung für einen Standortnamen. Wenn Sie beispielsweise "Frankfurt" angeben, gibt Bing Maps "Frankfurt am Main, Frankfurt, HE, Deutschland", "Frankfurt (Oder), BB, Deutschland" und "Frankfurt, BY, Deutschland" als mögliche Standorte zurück. Anschließend füllt TripOptimizerImpl::ProcessLocation das entsprechende Node-Objekt für jede Ressource mit dem Breiten- und Längengrad des Standorts auf. Wenn mehr als eine Ressource zurückgegeben wird, fügt die TripOptimizerImpl::ProcessLocation-Methode den Knoten der OptimizeTripParams::UnresolvedLocations-Variable hinzu.

// If there is only a single name, set it as the resolved name and 
// location.
if (node->Names.size() == 1)
{
    node->ResolvedLocation = node->Locations.front();
    node->ResolvedName = node->Names.front();
}
// Otherwise, add the node to the list of unresolved locations.
else if (node->ResolvedName.length() == 0)
{
    unresolvedLocations.push_back(node);
}

Wenn die OptimizeTripParams::UnresolvedLocations-Variable keine Elemente enthält, wechselt die TripOptimizerImpl::InternalOptimizeTripAsync-Methode zur zweiten Phase, in der Routendaten von Bing Maps abgerufen werden.

Weitere Informationen zum Bing Maps-Speicherortdienst finden Sie unter Standort-API.

Phase 2: Abrufen von Routendaten

In der zweiten Phase ruft die TripOptimizerImpl::InternalOptimizeTripAsync-Methode Routendaten von Bing Maps ab. Diese Routendaten werden abgerufen, da für den Reiseoptimierungsalgorithmus die Entfernung zwischen den verschiedenen Punkten im Diagramm erforderlich ist. Beachten Sie, dass ein Rand zwei Knoten des Diagramms verbindet und jeder Knoten einen Standort darstellt.

//
// Phase 2: Retrieve route information for each pair of locations.
//

// Report progress.
reporter.report("Retrieving routes (0% complete)...");

auto tasks = RetrieveRoutesAsync(params, cancellationToken, reporter);

// Move to the next phase after all current tasks complete.
return when_all(begin(tasks), end(tasks)).then(
    [=](task<void> t) -> task<IMap<String^, IVector<String^>^>^>
{
    // The PPL requires that all exceptions be caught and handled.
    // If any task in the collection errors, ensure that all errors in the entire
    // collection are observed at least one time.
    try
    {
        // Calling task.get will cause any exception that occurred 
        // during the task to be thrown.
        t.get();
    }
    catch (Exception^)
    {
        observe_all_exceptions<void>(begin(tasks), end(tasks));
        // Rethrow the original exception.
        throw;
    }
    catch (const task_canceled&)
    {
        observe_all_exceptions<void>(begin(tasks), end(tasks));
        // Rethrow the original exception.
        throw;
    }

    // Report progress.
    reporter.report("Retrieving routes (100% complete)...");

    // Record the elapsed HTTP time.
    params->HttpTime = GetTickCount64() - params->HttpTime;

Die TripOptimizerImpl::RetrieveRoutesAsync-Methode folgt einem ähnlichen Muster wie die TripOptimizerImpl::RetrieveLocationsAsync-Methode, um Routendaten von Bing Maps abzurufen.

// Retrieves distance information for each pair of locations from the Bing Maps route service.
vector<task<void>> TripOptimizerImpl::RetrieveRoutesAsync(
    shared_ptr<OptimizeTripParams> params,
    cancellation_token cancellationToken,
    progress_reporter<String^> reporter)
{   
    // Holds the tasks that process the returned XML documents.
    vector<task<void>> tasks;

    // Implementation note:
    // We assume that the route from A -> B is the same *distance* as 
    // the route from B -> A. Although this enables us to make fewer HTTP route requests,
    // the final route might be slightly sub-optimal if the trip contains legs with 
    // one-way streets or the distance from A -> B differs from the distance from B -> A.
    // (However, the end route will always contain the correct turn information.)

    // Create HTTP requests for route information.
    auto edges = params->Edges;
    params->RequestsPending = static_cast<long>(edges.size()); // Used to report progress.
    for (auto edge : edges)
    {
        // Create request URL.
        LatLong pointA = edge->PointA->ResolvedLocation;
        LatLong pointB = edge->PointB->ResolvedLocation;

        wstringstream uri;
        uri << L"http://dev.virtualearth.net/REST/v1/Routes/" << params->TravelMode
            << L"?wp.0=" << pointA.Latitude << L"," << pointA.Longitude
            << L"&wp.1=" << pointB.Latitude << L"," << pointB.Longitude
            << L"&optmz=" << params->Optimize
            << L"&o=xml"
            << L"&key=" << params->BingMapsKey;

        // Create a parent task that downloads the XML document.
        auto httpRequest = make_shared<HttpRequest>();
        auto downloadTask = httpRequest->GetAsync(
            ref new Uri(ref new String(uri.str().c_str())), 
            cancellationToken);

        // Create a continuation task that fills route information after 
        // the download finishes.
        tasks.push_back(downloadTask.then([=](task<wstring> previousTask)
        {
            (void)httpRequest;

            // Get the result to force exceptions to be thrown.
            wstring response = previousTask.get();

            try
            {
                // Create and load the XML document from the response.
                XmlDocument^ xmlDocument = ref new XmlDocument();
                auto xml = ref new String(response.c_str() + 1); // Bypass BOM.
                xmlDocument->LoadXml(xml);

                // Fill in route information.
                ProcessRoute(edge, xmlDocument);
            }
            catch (Exception^)
            {
                // An error occurred. Cancel any other active downloads.
                m_cancellationTokenSource.cancel();
                // Rethrow the exception.
                throw;
            }

            // Report progress.
            wstringstream progress;
            progress << L"Retrieving routes ("
                << static_cast<long>(100.0 * (params->Edges.size() - params->RequestsPending) / params->Edges.size())
                << L"% complete)...";
            reporter.report(ref new String(progress.str().c_str()));
            InterlockedDecrement(&params->RequestsPending);
        }));
    }

    return tasks;
}

Die TripOptimizerImpl::ProcessRoute-Methode folgt einem Muster, das der TripOptimizerImpl::ProcessLocation-Methode zum Laden von XML-Daten ähnelt. Der Unterschied besteht darin, dass die TripOptimizerImpl::ProcessRoute-Methode Routeninformationen in ein Edge-Objekt für ein Standortpaar lädt.

//
// Update edges.

// Set travel distance.
edge->TravelDistance = travelDistance;

// Ensure that the distance is at least FLT_EPSILON.
// If the travel distance is very short, a value below FLT_EPSILON
// can result in a divide by zero error in the trip optimization algorithm.
if (edge->TravelDistance < FLT_EPSILON)
{
    edge->TravelDistance = FLT_EPSILON;
}

// Set latitude and longitude of both points.
edge->PointA->ResolvedLocation = LatLong(lat0, lon0);
edge->PointB->ResolvedLocation = LatLong(lat1, lon1);

Nachdem die TripOptimizerImpl::RetrieveRoutesAsync-Methode alle Routeninformationen verarbeitet hat, führt die TripOptimizerImpl::InternalOptimizeTripAsync-Methode die Endphase aus, in der die Routenoptimierung erfolgt.

Weitere Informationen über den Bing Maps-Routendienst finden Sie unter Routen-API

Phase 3: Berechnen der optimierten Route

In der dritten Phase optimiert die TripOptimizerImpl::InternalOptimizeTripAsync-Methode die Route für die kürzeste Gesamtstrecke. Sie ruft die AntSystem::OptimizeRoute-Funktion auf, die die optimierte Reiseroute mithilfe von Knoten und Randinformationen sowie anderen Parametern, wie Eingaben für den Ameisenalgorithmus, berechnet.

// Run the simulation.
vector<size_t> routeIndices = OptimizeRoute(
    params->Nodes, params->Edges, 
    params->Alpha, params->Beta, params->Rho, 
    params->Iterations, 
    cancellationToken,
    &progressCallback, 
    params->Parallel);

Wenn die AntSystem::OptimizeRoute-Funktion zurückgegeben wird, dreht die TripOptimizerImpl::InternalOptimizeTripAsync-Methode die Reihenfolge entsprechend den Benutzereingaben um. Das heißt, es wird sichergestellt, dass der erste Eintrag des Benutzers der erste Eintrag in der optimierten Route ist.

// Create the final route.
// The optimizer returns a route that has an arbitrary starting point.
// For example, the route might look like:
// A -> B -> C -> D -> E -> A
// If our starting point was D, we want the route to look like:
// D -> E -> A -> B -> C -> D
routeIndices.pop_back();
while (routeIndices.front() != 0)
{
    routeIndices.push_back(routeIndices.front());
    routeIndices.erase(begin(routeIndices));
}
routeIndices.push_back(routeIndices.front());

Die TripOptimizerImpl::InternalOptimizeTripAsync-Methode erstellt dann parallele Vektoren, die Standortdaten (Breitengrad und Längengrad) und Anzeigenamen enthalten. Diese Vektoren sind in einem Platform::Collections::Map-Objekt enthalten. (Map ist die C++-Implementierung für die Windows::Foundation::Collections::IMap<K, V>-Schnittstelle. Entsprechend ist Platform::Collections::Vector die C++-Implementierung für die Windows::Foundation::Collections::IVector<T>-Schnittstelle.) Die Haupt-App verwendet die Standortdaten, um die Karte und die Standortnamen im Rahmen der ausführlichen Streckenbeschreibung anzuzeigen.

//
// Prepare the return value.
//

// Parallel arrays that hold the optimized route locations and names.
IVector<String^>^ optimizedRoute;             // {"47.620056,-122.349261", ...}
IVector<String^>^ optimizedRouteDisplayNames; // {"Space Needle, WA", ...}

optimizedRoute = ref new Vector<String^>();
optimizedRouteDisplayNames = ref new Vector<String^>();

// Fill the arrays.
size_t i = 0;
for (size_t index : routeIndices)
{
    const auto node = params->Nodes[index];

    String^ v;

    // The location is the latitude and longitude of the waypoint.
    // For example, "47.620056,-122.349261"
    wstringstream location;
    location << node->ResolvedLocation.Latitude << L',' << node->ResolvedLocation.Longitude;

    v = ref new String(location.str().c_str());
    optimizedRoute->InsertAt(static_cast<unsigned int>(i), v);

    // The display name if the resolved name of the waypoint.
    // For example, "Space Needle, WA"
    v = ref new String(node->ResolvedName.c_str());
    optimizedRouteDisplayNames->InsertAt(static_cast<unsigned int>(i), v);

    ++i;
}

// The return value.
auto finalRoute = ref new Map<String^, IVector<String^>^>();

finalRoute->Insert("locations", optimizedRoute);
finalRoute->Insert("displayNames", optimizedRouteDisplayNames);

// Compute the overall elapsed time.
params->TotalTime = GetTickCount64() - params->TotalTime;

// Report final progress.
// This message contains the overall elapsed time, the time spent performing 
// HTTP requests, and the time it took to run the simulation.
wstringstream progress;
progress << L"Loading Map. Elapsed time: "
    << params->TotalTime << L"ms (total); "
    << params->HttpTime << L"ms (HTTP); "
    << params->SimulationTime << L"ms (simulation).";
reporter.report(ref new String(progress.str().c_str()));

return task_from_result<IMap<String^, IVector<String^>^>^>(finalRoute);

[Nach oben]

Definieren von HTTP-Funktionalität

Die C++-Komponente definiert die HttpRequest-Klasse, um HTTP-Anforderungen zu verarbeiten. Diese Klasse verwendet die Schnittstelle IXMLHTTPRequest2, um HTTP-Anforderungen zu verarbeiten. Die IXMLHTTPRequest2-Schnittstelle unterstützt nur asynchrone Vorgänge. Damit der Aufrufer diese asynchronen Vorgänge besser verarbeiten kann, gibt die HttpRequest::GetAsync-Methode ein concurrency::task<std::wstring>-Objekt zurück. Dieses Task-Objekt enthält die HTTP-Antwort als Zeichenfolge.

Hinweis

IXMLHTTPRequest2 ist eine Methode für die Verbindung mit dem Webdienst.Weitere Informationen zu den anderen Optionen für die Verbindung mit den Diensten in Ihrer App finden Sie unter Herstellen einer Verbindung mit Webdiensten.

Da IXMLHTTPRequest2 nur asynchrone Vorgänge unterstützt, müssen Sie ein IXMLHTTPRequest2Callback-Objekt bereitstellen, wenn Sie Daten von einem HTTP-Server anfordern. Die HttpRequest.cpp-Datei definiert die HttpRequestStringCallback-Klasse, die von dieser Schnittstelle erbt und deren Methoden implementiert.

Ein wichtiger Bestandteil dieser Implementierung ist die Verwendung von concurrency::task_completion_event. Diese Klasse ermöglicht der HttpReader-Klasse, eine Aufgabe zu erstellen, die festgelegt wird, wenn eine andere asynchrone Aufgabe abgeschlossen wird. Diese Klasse ist hilfreich, wenn Sie task-Objekte in Verbindung mit asynchronen Vorgängen erstellen müssen, die durch Rückrufe abgeschlossen werden. Wenn der Downloadvorgang erfolgreich abgeschlossen wird, legt die HttpRequestStringCallback::OnResponseReceived-Methode das Abschlussereignis fest.

completionEvent.set(make_tuple<HRESULT, wstring>(move(hr), move(wstr)));

Entsprechend legt die HttpRequestStringCallback::OnError-Methode das Abschlussereignis fest, wenn ein Fehler auftritt. In diesem Fall sind der Fehlercode und die leere Zeichenfolge das Ergebnis der Aufgabe.

completionEvent.set(make_tuple<HRESULT, wstring>(move(hrError), wstring()));

Die HttpRequest::GetAsync-Methode ruft HttpRequest::DownloadAsync auf. Die HttpRequest::DownloadAsync-Methode öffnet die asynchrone Anforderung und erstellt ein HttpRequestStringCallback-Objekt. Sie erstellt dann ein task-Objekt, das abgeschlossen wird, wenn das Aufgabenabschlussereignis des HttpRequestStringCallback-Objekts abgeschlossen wird. Dieses task-Objekt gibt das HttpRequestStringCallback-Objekt mithilfe einer Fortsetzung frei, nachdem das Aufgabenabschlussereignis abgeschlossen ist.

// Start a download of the specified URI using the specified method.  The returned task produces the
// HTTP response text.  The status code and reason can be read with GetStatusCode() and GetReasonPhrase().
task<wstring> HttpRequest::DownloadAsync(PCWSTR httpMethod, PCWSTR uri, cancellation_token cancellationToken,
    PCWSTR contentType, IStream* postStream, uint64 postStreamSizeToSend)
{
    // Create an IXMLHTTPRequest2 object.
    ComPtr<IXMLHTTPRequest2> xhr;
    CheckHResult(CoCreateInstance(CLSID_XmlHttpRequest, nullptr, CLSCTX_INPROC, IID_PPV_ARGS(&xhr)));

    // Create callback.
    auto stringCallback = Make<HttpRequestStringCallback>(xhr.Get(), cancellationToken);
    CheckHResult(stringCallback ? S_OK : E_OUTOFMEMORY);

    auto completionTask = create_task(stringCallback->GetCompletionEvent());

    // Create a request.
    CheckHResult(xhr->Open(httpMethod, uri, stringCallback.Get(), nullptr, nullptr, nullptr, nullptr));

    if (postStream != nullptr && contentType != nullptr)
    {
        CheckHResult(xhr->SetRequestHeader(L"Content-Type", contentType));
    }

    // Send the request.
    CheckHResult(xhr->Send(postStream, postStreamSizeToSend));

    // Return a task that completes when the HTTP operation completes. 
    // We pass the callback to the continuation because the lifetime of the 
    // callback must exceed the operation to ensure that cancellation 
    // works correctly.
    return completionTask.then([this, stringCallback](tuple<HRESULT, wstring> resultTuple)
    {
        // If the GET operation failed, throw an Exception.
        CheckHResult(std::get<0>(resultTuple));

        statusCode = stringCallback->GetStatusCode();
        reasonPhrase = stringCallback->GetReasonPhrase();

        return std::get<1>(resultTuple);
    });
}

Informationen darüber, wie die TripOptimizerImpl-Klasse die optimierte Route anhand der resultierenden XML-Daten berechnet, finden Sie unter Komponentenworkflow in diesem Dokument. Weitere Beispiele für die Verwendung von IXMLHTTPRequest2 finden Sie unter Quickstart: Connecting using XML HTTP Request und Exemplarische Vorgehensweise: Verbinden von Verwendungsaufgaben und XML-HTTP-Anforderungen.

[Nach oben]

Berechnen der optimalen Route

Der Kernalgorithmus, der die Routenberechnung ausführt, wird in AntSystem.h und in AntSystem.cpp definiert. Die Routenberechnung ähnelt dem Problem des Handlungsreisenden. Das Ziel des Problems des Handlungsreisenden ist, anhand einer Auflistung von Standorten und der Entfernung zwischen den einzelnen Standorten die kürzeste Route zu berechnen, bei der jeder Standort nur einmal besucht wird. Das Problem des Handlungsreisenden war schon immer schwierig zu lösen, da jede mögliche Route berechnet werden muss, um die optimale Route zu ermitteln. Der Ameisenalgorithmus ist ein metaheuristischer Ansatz zur Lösung von Problemen dieser Art. Er modelliert das Verhalten von Ameisen, um eine optimierte Route schnell zu ermitteln. Obwohl die von diesem Algorithmus ermittelten Routen für eine bestimmte Gruppe von Standorten nicht garantiert die kürzesten sein müssen, wird dennoch häufig tatsächlich die kürzeste Route oder zumindest eine Route ermittelt, die für Reisezwecke kurz genug ist.

Die AntSystem.h- und AntSystem.cpp-Dateien definieren den AntSystem-Namespace. Dieser Namespace enthält keine Abhängigkeiten von Windows-Runtime und verwendet daher C++/CX nicht. Die AntSystem.h-Datei definiert die LatLong-, Node- und Edge-Strukturen. Außerdem definiert sie die OptimizeRoute-Funktion.

Die LatLong-Struktur stellt den Breiten- und Längengrad eines Punkts auf einer Karte dar.

// Represents the latitude and longitude of a single point on a map.
struct LatLong
{
    explicit LatLong(double latitude, double longitude) 
        : Latitude(latitude)
        , Longitude(longitude)
    {
    }

    // The coordinates of the location.
    double Latitude;
    double Longitude;
};

Die Node-Struktur stellt einen Knoten in einem Diagramm dar. Sie enthält den Namen, den Breiten- und den Längengrad eines Standorts. Außerdem enthält sie alternative Namen, die vom Bing Maps-Dienst stammen.

// Represents a node in a graph.
struct Node 
{
    explicit Node(const std::wstring& inputName)
        : InputName(inputName)
        , ResolvedLocation(0.0, 0.0)
    {
    }

    // The name of the location as provided by the user.
    std::wstring InputName;
    // The resolved latitude and longitude of the location as provided by the 
    // Bing Maps location service.
    LatLong ResolvedLocation;
    // The resolved name of the location as provided by the 
    // Bing Maps location service.
    std::wstring ResolvedName;

    //
    // Parallel arrays of string names and latitude, longitude pairs that represent
    // all possible resolved locations for the current input name.
    // For example, if the input name is "Redmond", the Names array might contain
    // "Redmond, WA", "Redmond, OR", "Redmond, UT", and "Redmond, Australia".
    // The Locations array would contain the corresponding latitude and longitude
    // for each location.
    std::vector<std::wstring> Names;
    std::vector<LatLong> Locations;
};

Die Edge-Struktur verbindet zwei Knoten und enthält die Entfernung zwischen diesen Knoten. Sie enthält auch Daten, die vom Ameisenalgorithmus verwendet werden.

// Represents an edge in a graph of Node objects.
// An Edge object connects two nodes and holds the travel distance between 
// those nodes. An Edge object also holds the amount of pheromone that 
// exists on that edge.
struct Edge
{
    explicit Edge(std::shared_ptr<Node> pointA, std::shared_ptr<Node> pointB)
        : PointA(pointA)
        , PointB(pointB)
        , Pheromone(0.0)
        , TravelDistance(-1.0)
    {
    }

    // The start node.
    std::shared_ptr<Node> PointA;
    // The end node.
    std::shared_ptr<Node> PointB;
    // The amount of pheromone on the edge.
    double Pheromone;
    // The distance from the start node to the end node.
    double TravelDistance;
};

Die C++-Komponente erstellt ein Node-Objekt für jeden Standort der Route und ein Edge-Objekt für jedes Standortpaar. Nachdem die Komponente alle erforderlichen Informationen aus den Webdiensten von Bing Maps erfasst hat, ruft sie OptimizeRoute auf, um die optimale Route zu berechnen.

// Optimizes the route among the given nodes for the shortest travel distance.
// This method returns indicies to the provided Node collection.
std::vector<size_t> OptimizeRoute(
    std::vector<std::shared_ptr<Node>>& nodes,
    std::vector<std::shared_ptr<Edge>>& edges,
    double alpha,
    double beta,
    double rho,
    unsigned int iterations,
    Concurrency::cancellation_token cancellationToken,
    std::function<void(unsigned int)>* progressCallback = nullptr,
    bool parallel = true);

Aus Platzgründen wird der Ameisenalgorithmus in dieser Dokumentation nicht ausführlich beschrieben. Ausführliche Informationen finden Sie unter "AntSystem.cpp" im Quellcode.

Ein wichtiger Aspekt der Implementierung des Algorithmus besteht jedoch in der Verwendung von Parallelität. Der Ameisenalgorithmus führt mehrere Iterationen in drei grundlegenden Schritten aus: Jede Ameise darf das Diagramm bereisen, Pheromone abgeben und dann ihre Schritte zurück zum Anfangspunkt verfolgen. Der erste Schritt, bei dem jede Ameise das Diagramm bereisen darf, kann parallel ausgeführt werden, da jede Ameise unabhängig agiert. Dieser Schritt enthält keine freigegebenen Daten oder abhängigen Berechnungen.

// Perform the simulation several times.
auto startTime = GetTickCount64();
for (unsigned int i = 0; i < iterations; ++i)
{
    // Occasionally check for cancellation.
    auto time = GetTickCount64();
    if (time - startTime > 100) 
    {
        if (cancellationToken.is_canceled())
        {
            // Return the empty collection.
            return vector<size_t>();
        }
        startTime = time;
    }

    // Send progress. 
    if (progressCallback != nullptr)
    {
        (*progressCallback)(i);
    }

    // 
    // Allow each ant to perform a tour of the graph.
    // Note that this operation can be performed in parallel because each ant acts independently.
    // This step contains no shared data or dependent computations.
    if (parallel)
    {
        parallel_for_each(begin(ants), end(ants), [&](Ant& blitz)
        {
            blitz.Explore();
        });
    }
    else
    {
        for_each(begin(ants), end(ants), [&](Ant& blitz)
        {
            blitz.Explore();
        });
    }

    //
    // Evaporate pheromone.
    for_each(begin(edges), end(edges), [rho](shared_ptr<Edge> edge)
    {
        edge->Pheromone *= (1.0 - rho);
    });

    // 
    // Allow each ant to backtrack through the graph and drop pheromone on 
    // each edge.
    //
    // Note that this operation is NOT performed in parallel because 
    // the ants update the pherone value of each edge.
    // Because the backtrack operation is not relatively lengthy, the 
    // overhead that is required to synchronize access to the edges would 
    // likely outweigh any benefits of parallel processing.
    for_each(begin(ants), end(ants), [&](Ant& blitz)
    {
        blitz.Backtrack();
    });
}

Weitere Informationen zu parallelen Algorithmen wie parallel_for_each finden Sie unter Parallele Algorithmen.

Hinweis

Die Verwendung des parallel-Flags ist für die Implementierung nicht zwingend erforderlich.Es wird als Option auf der Benutzeroberfläche bereitgestellt, damit Sie mit der parallelen Berechnung im Vergleich zur seriellen Berechnung leichter experimentieren können.

[Nach oben]

Behandlung von Abbrüchen

Die IAsyncAction-, IAsyncActionWithProgress<TProgress>-, IAsyncOperation<TResult>- und IAsyncOperationWithProgress<TResult, TProgress>-Schnittstellen bieten jeweils eine Cancel-Methode, die es Ihnen ermöglicht, den asynchronen Vorgang abzubrechen. In C++ brechen diese Cancel-Methoden ein Abbruchtoken ab, das dem asynchronen Vorgang zugeordnet ist. Es gibt zwei Möglichkeiten, den Aufgabenabbruch mit den Windows-Runtime Cancel-Methoden zu verbinden. Die erste Möglichkeit besteht darin, die Arbeitsfunktion zu definieren, die Sie an create_async übergeben, um ein concurrency::cancellation_token-Objekt zu verwenden. Wenn die Cancel-Methode aufgerufen wird, wird dieses Abbruchtoken abgebrochen und die normalen Abbruchregeln gelten. Wenn Sie kein cancellation_token-Objekt bereitstellen, wird es vom zugrunde liegenden task-Objekt implizit definiert. Definieren Sie ein cancellation_token-Objekt, wenn Sie auf Abbrüche in der Arbeitsfunktion kooperativ reagieren müssen. Weitere Informationen zu diesem Abbruchmechanismus finden Sie unter Erstellen von asynchronen Vorgängen in C++ für Windows Store-Apps.

Ein Abbruch tritt auf, wenn der Benutzer die Schaltfläche Cancel in der JavaScript-App auswählt oder ein nicht behebbarer Fehler auftritt. Damit der Benutzer einen Vorgang abbrechen kann, muss die Benutzeroberfläche während der Optimierungsaufgabe reaktionsfähig bleiben. Der Abbruch erfolgt nicht unmittelbar. Die C++-Komponente verwendet concurrency::cancellation_token_source und concurrency::cancellation_token, um den Abbruch zu signalisieren und regelmäßige Prüfungen auf Abbrüche durchzuführen. Die C++-Komponente implementiert Abbrüche auf einer möglichst groben Ebene, versucht aber dennoch, den Abbruch möglichst zeitnah auszuführen. Im Hinblick auf die Leistung würde die App nicht von zu häufigen Überprüfungen auf Abbrüche profitieren. Tatsächlich kann die Leistung beeinträchtigt werden, wenn die Zeit für die Überprüfung auf Abbrüche die Arbeitszeit übersteigt.

Die C++-Komponente führt zwei verschiedene Überprüfungen auf Abbrüche durch. Zuerst die Fortsetzungsaufgabe, die auftritt, nachdem eine Optimierungsphase concurrency::task::get aufgerufen hat, um eine Überprüfung auf Abbrüche durchzuführen. Die task::get-Methode löst jede Ausnahme aus, die während der Aufgabe aufgetreten ist, einschließlich task_canceled, wenn ein Abbruch aufgetreten ist. (Bei when_all wählt die Laufzeit eine der Ausnahmen aus, wenn mehrere Aufgaben ausgelöst wurden.) Da alle auftretenden Aufgabenausnahmen beachtet werden müssen, definieren wir die observe_all_exceptions-Funktion zur Beobachtung aller Ausnahmen, die in den für den when_all-Algorithmus bereitgestellten Aufgaben aufgetreten sind. Im folgenden Beispiel wird die Überprüfung auf Abbrüche dargestellt, nachdem Standorte von Bing Maps abgerufen wurden und bevor Routen abgerufen werden.

//
// Phase 2: Retrieve route information for each pair of locations.
//

// Report progress.
reporter.report("Retrieving routes (0% complete)...");

auto tasks = RetrieveRoutesAsync(params, cancellationToken, reporter);

// Move to the next phase after all current tasks complete.
return when_all(begin(tasks), end(tasks)).then(
    [=](task<void> t) -> task<IMap<String^, IVector<String^>^>^>
{
    // The PPL requires that all exceptions be caught and handled.
    // If any task in the collection errors, ensure that all errors in the entire
    // collection are observed at least one time.
    try
    {
        // Calling task.get will cause any exception that occurred 
        // during the task to be thrown.
        t.get();
    }
    catch (Exception^)
    {
        observe_all_exceptions<void>(begin(tasks), end(tasks));
        // Rethrow the original exception.
        throw;
    }
    catch (const task_canceled&)
    {
        observe_all_exceptions<void>(begin(tasks), end(tasks));
        // Rethrow the original exception.
        throw;
    }

    // Report progress.
    reporter.report("Retrieving routes (100% complete)...");

    // Record the elapsed HTTP time.
    params->HttpTime = GetTickCount64() - params->HttpTime;

Nach dem Aufruf von observe_all_exceptions wird die ursprüngliche Ausnahme erneut ausgelöst, damit sie vom Code verarbeitet werden kann, der von dieser Aufgabe abhängig ist.

Im Folgenden wird die observe_all_exceptions-Funktion veranschaulicht. Die Funktion durchläuft jedes task-Objekt in der bereitgestellten Auflistung und verwendet die task::get-Methode zur Prüfung auf Fehler. Da eine der Ausnahmen später erneut ausgelöst werden soll, werden leere catch-Blöcke verwendet, um anzugeben, dass die Ausnahme beachtet und bearbeitet wurde.

// Observes all exceptions that occurred in all tasks in the given range.
template<class T, class InIt>
void observe_all_exceptions(InIt first, InIt last)
{
    for_each (first, last, [](task<T> t)
    {
        t.then([](task<T> previousTask)
        {
            try
            {
                previousTask.get();
            }
            catch (Exception^)
            {
                // Swallow the exception.
            }
            catch (const exception&)
            {
                // Swallow the exception.
            }
        });
    });
}

Die zweite Methode zur Überprüfung der Vorgänge auf Abbrüche besteht im Aufrufen der concurrency::cancellation_token::is_canceled-Methode. Der Reiseoptimierungsalgorithmus (die AntSystem::OptimizeRoute-Funktion) führt so alle 100 Millisekunden eine Überprüfung auf Abbrüche durch.

// Perform the simulation several times.
auto startTime = GetTickCount64();
for (unsigned int i = 0; i < iterations; ++i)
{
    // Occasionally check for cancellation.
    auto time = GetTickCount64();
    if (time - startTime > 100) 
    {
        if (cancellationToken.is_canceled())
        {
            // Return the empty collection.
            return vector<size_t>();
        }
        startTime = time;
    }

Hinweis

Es hätte auch das erste Verfahren, also is_task_cancellation_requested und cancel_current_task statt cancellation_token::is_canceled aufzurufen, verwendet werden können.cancel_current_task muss jedoch von einem task-Objekt aufgerufen werden.Da Sie diese Implementierung theoretisch verwenden können, um die AntSystem::OptimizeRoute-Funktion von task oder von einem anderen Teil des Codes aufzurufen, werden Abbruchtoken aus Gründen der Flexibilität direkt verwendet.Wenn diese Funktion von Code aufgerufen werden soll, der keine Aufgaben verwendet, können Sie concurrency::cancellation_token::none für den cancellationToken-Parameter übergeben.Das none-Token kann nicht abgebrochen werden.

Der Abschnitt Definieren von HTTP-Funktionalität beschreibt, wie die HttpRequestStringCallback-Klasse task_completion_event verwendet, um asynchrone Vorgänge zu erstellen, die mithilfe von Rückrufen in Verbindung mit task-Objekten abgeschlossen werden. Zur Unterstützung von Abbrüchen verwendet die HttpRequestStringCallback-Klasse entsprechend die concurrency::cancellation_token::register_callback-Methode, um eine Rückruffunktion zu registrieren, die aufgerufen wird, wenn das Abbruchtoken abgebrochen wird. Dieses Verfahren ist hilfreich, da die IXMLHTTPRequest2-Schnittstelle asynchrone Aufgaben ausführt, die sich unserer Kontrolle entziehen. Wenn das Abbruchtoken abgebrochen wird, bricht die Rückruffunktion die HTTP-Anforderung ab und legt das Aufgabenabschlussereignis fest.

HttpRequestStringCallback(IXMLHTTPRequest2* r, cancellation_token ct) :
    request(r), cancellationToken(ct)
{
    // Register a callback function that aborts the HTTP operation when 
    // the cancellation token is canceled.
    if (cancellationToken != cancellation_token::none())
    {
        registrationToken = cancellationToken.register_callback([this]() 
        {
            if (request != nullptr) 
            {
                request->Abort();
            }
        });
    }
}

cancellation_token::register_callback gibt ein concurrency::cancellation_token_registration-Objekt zurück, das die Rückrufregistrierung identifiziert. Der Destruktor der HttpRequest-Klasse verwendet dieses Registrierungsobjekt, um die Registrierung der Rückruffunktion aufzuheben. Es wird empfohlen, die Registrierung des Rückrufs immer aufzuheben, wenn Sie ihn nicht mehr benötigen, um sicherzustellen, dass alle Objekte gültig sind, wenn eine Rückruffunktion aufgerufen wird.

~HttpRequestStringCallback()
{
    // Unregister the callback.
    if (cancellationToken != cancellation_token::none())
    {
        cancellationToken.deregister_callback(registrationToken);
    }
}

Im Falle eines nicht behebbaren Fehlers werden alle verbleibenden Aufgaben abgebrochen. Wenn beispielsweise ein XML-Dokument nicht verarbeitet werden kann, wird der gesamte Vorgang abgebrochen und die Ausnahme erneut ausgelöst.

try
{
    // Create and load the XML document from the response.
    XmlDocument^ xmlDocument = ref new XmlDocument();
    auto xml = ref new String(response.c_str() + 1); // Bypass BOM.
    xmlDocument->LoadXml(xml);

    // Fill in location information.
    ProcessLocation(node, xmlDocument, params->UnresolvedLocations);
}
catch (Exception^)
{
    // An error occurred. Cancel any active operations.
    m_cancellationTokenSource.cancel();
    // Rethrow the exception.
    throw;
}

Die TripOptimizerImpl-Klasse definiert ein concurrency::cancellation_token_source-Objekt, da der Abbruch von dieser Klasse initiiert wird. Damit der Abbruch der Aufgaben sowohl über die Schaltfläche Cancel als auch über den internen Code erfolgen kann, ruft die TripOptimizerImpl-Klasse die concurrency::cancellation_token_source::create_linked_source-Methode auf. Mithilfe dieser verknüpften Abbruchtokenquelle kann dasselbe Abbruchtoken sowohl von der JavaScript-App als auch von der TripOptimizerImpl-Klasse abgebrochen werden, jedoch aus verschiedenen cancellation_token_source-Objekten heraus.

// Perform the operation asynchronously.
return create_async([this, params](progress_reporter<String^> reporter, 
    cancellation_token cancellationToken) -> task<IMap<String^, IVector<String^>^>^>
{
    // Create a linked source for cancellation.
    // This enables both the caller (through the returned 
    // IAsyncOperationWithProgress object) and this class to set
    // the same cancellation token.
    m_cancellationTokenSource = 
        cancellation_token_source::create_linked_source(cancellationToken);

Weitere Informationen dazu, wie Abbrüche in der Parallel Patterns Library funktionieren, finden Sie unter Abbruch in der PPL.

[Nach oben]

Migration von ActiveX

Informationen darüber, wie Sie von der ActiveX-Version des Reise-Optimierer von Bing Maps zu einer Windows Store-App migrieren, finden Sie unter Migrieren von vorhandenem Code am Beispiel des Trip-Optimierers von Bing Maps.

[Nach oben]

Nächste Schritte

Informationen darüber, wie die Windows-Runtime-Komponente in C++ mit der JavaScript-Komponente interagiert, finden Sie unter Interoperation zwischen JavaScript und C++ am Beispiel des Reise-Optimierers von Bing Maps.

[Nach oben]

Siehe auch

Konzepte

Interoperation zwischen JavaScript und C++ am Beispiel des Reise-Optimierers von Bing Maps

Verwenden von JavaScript am Beispiel des Reise-Optimierers von Bing Maps

Weitere Ressourcen

Entwickeln des Reise-Optimierers von Bing Maps, einer Windows Store-App in JavaScript und C++